fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define Long long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. struct DSU {
  10.     vector<int> parent, count;
  11.  
  12.     void init(int n) {
  13.         count.assign(n, 1), parent.assign(n, 0);
  14.         for (int i = 0; i < n; ++i) parent[i] = i;
  15.     }
  16.  
  17.     int root(int u) {
  18.         while (u != parent[u])
  19.             u = parent[u] = parent[parent[u]];
  20.         return u;
  21.     }
  22.  
  23.     void merge(int u, int v) {
  24.         int uroot = root(u), vroot = root(v);
  25.         if (uroot == vroot) return;
  26.         if (count[uroot] < count[vroot]) swap(uroot, vroot);
  27.         count[uroot] += count[vroot], parent[vroot] = uroot;
  28.     }
  29. };
  30.  
  31. void getShitDone() {
  32.     int n, m;
  33.     cin >> n >> m;
  34.  
  35.     vector< vector< array<int, 2> > > adj(m);
  36.     for (int i = 0, u, v, c; i < m; ++i) {
  37.         cin >> u >> v >> c; --u, --v, --c;
  38.         adj[c].push_back({ u, v });
  39.     }
  40.  
  41.     int q;
  42.     cin >> q;
  43.     int sq = sqrt(q) + 1;
  44.  
  45.     vector<int> ans(q);
  46.     vector< vector< pair<int, int> > > with(n);
  47.     for (int i = 0, u, v; i < q; ++i) {
  48.         cin >> u >> v; --u, --v;
  49.         if (u > v) swap(u, v);
  50.         with[u].push_back({ v, i });
  51.     }
  52.  
  53.     int countBig = 0;
  54.     vector<int> mp(n, -1);
  55.     vector< vector< pair<int, int> > > big;
  56.     for (int i = 0; i < n; ++i) {
  57.         if ( with[i].size() > sq ) {
  58.             mp[i] = countBig++, big.push_back({});
  59.             for (auto [u, id] : with[i]) {
  60.                 if ( with[u].size() > sq ) {
  61.                     big.back().push_back({ u, id });
  62.                 } else if (u > i) {
  63.                     with[u].push_back({ i, id });
  64.                 }
  65.             }
  66.         }
  67.     }
  68.  
  69.     vector<int> vis(n);
  70.     DSU solve; solve.init(n);
  71.     for (int i = 0, vid = 1; i < m; ++i, ++vid) {
  72.         if ( adj[i].empty() ) continue;
  73.  
  74.         vector<int> nodes;
  75.         for (auto [u, v] : adj[i]) {
  76.             solve.merge(u, v);
  77.             if (vis[u] != vid)
  78.                 vis[u] = vid, nodes.push_back(u);
  79.             if (vis[v] != vid)
  80.                 vis[v] = vid, nodes.push_back(v);
  81.         }
  82.  
  83.         for (int v : nodes) {
  84.             if ( with[v].size() <= sq ) {
  85.                 for (auto [u, id] : with[v])
  86.                     if ( solve.root(u) == solve.root(v) ) ++ans[id];
  87.             } else {
  88.                 for (auto [u, id] : big[ mp[v] ])
  89.                     if ( solve.root(u) == solve.root(v) ) ++ans[id];
  90.             }
  91.         }
  92.  
  93.         for (int v : nodes)
  94.             solve.parent[v] = v, solve.count[v] = 1;
  95.     }
  96.  
  97.     for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
  98. }
  99.  
  100. signed main() {
  101.     _3bkarm
  102.  
  103.     int ts = 1;
  104. //    cin >> ts;
  105.     while (ts--) getShitDone();
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5FZKxk
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!