Instantly share code, notes, and snippets.

# NSTomoS/ABC040D.cpp Created Jul 8, 2016

What would you like to do?
 #include #include using namespace std; class UnionFind { vector pir; public: UnionFind(int size) : pir(size, -1) { } void unite(int x, int y) { x = root(x); y = root(y); if (x != y) { if (pir[y] < pir[x]) swap(x, y); pir[x] += pir[y]; pir[y] = x; } } bool same(int x, int y) { return root(x) == root(y); } int root(int x) { if (pir[x] < 0) { return x; } else { return pir[x] = root(pir[x]); } } int size(int x) { return -pir[root(x)]; } }; signed main(signed argc, char *argv[]) { int n, m; cin >> n >> m; vector a(m), b(m), y(m); for (int i = 0; i < m; ++i) { cin >> a[i] >> b[i] >> y[i]; a[i]--; b[i]--; } int q; cin >> q; vector v(q), w(q); for (int i = 0; i < q; ++i) { cin >> v[i] >> w[i]; v[i]--; } vector>> edge(200001); for (int i = 0; i < m; ++i) { edge[y[i]].push_back(make_pair(a[i], b[i])); } vector>> query(200001); for (int i = 0; i < q; ++i) { query[w[i]].push_back(make_pair(v[i], i)); } vector ans(q); UnionFind uf(n); for (int i = 200000; i >= 0; --i) { for (int j = 0; j < (int) query[i].size(); ++j) { ans[query[i][j].second] = uf.size(query[i][j].first); } for (int j = 0; j < (int) edge[i].size(); ++j) { uf.unite(edge[i][j].first, edge[i][j].second); } } for (int i = 0; i < q; ++i) { cout << ans[i] << endl; } return 0; }