# USACO 2018 January Contest, Gold Problem 1. MooTube

Apr 15th, 2021
511
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. ifstream fin("mootube.in");
6. ofstream fout("mootube.out");
7.
8. struct edge {
9.   int u, v, w;
10.
12.     fin >> u >> v >> w;
13.   }
14.
15.   bool operator < (const edge &A) const {
16.     return w > A.w;
17.   }
18. };
19.
20. struct qry {
21.   int k, v, ind;
22.
23.   bool operator < (const qry &A) const {
24.     return k > A.k;
25.   }
26. };
27.
28. struct DSU {
29.   vector<int> p, r;
30.
31.   DSU(int N) {
32.     p.resize(N + 1);
33.     r.assign(N + 1, 1);
34.     iota(p.begin(), p.end(), 0);
35.   }
36.
37.   int get(int x) {
38.     if (x == p[x])
39.       return x;
40.     return p[x] = get(p[x]);
41.   }
42.
43.   int get_size(int u) {
44.     return r[get(u)];
45.   }
46.
47.   bool unite(int u, int v) {
48.     int x = get(u), y = get(v);
49.     if (x == y)
50.       return false;
51.     if (r[x] > r[y]) {
52.       p[y] = x;
53.       r[x] += r[y];
54.     } else {
55.       p[x] = y;
56.       r[y] += r[x];
57.     }
58.     return true;
59.   }
60. };
61.
62. void solve() {
63.   int N, Q;
64.   fin >> N >> Q;
65.   vector<edge> edges(N - 1);
66.   for (edge &e : edges)
68.   sort(edges.begin(), edges.end());
69.   vector<qry> queries(Q);
70.   for (int i = 0; i < Q; ++i) {
71.     fin >> queries[i].k >> queries[i].v;
72.     queries[i].ind = i;
73.   }
74.   sort(queries.begin(), queries.end());
75.   vector<int> sol(Q);
76.   int p = 0;
77.   DSU tree(N);
78.   for (const qry &q : queries) {
79.     while (p < N - 1 && edges[p].w >= q.k) {
80.       tree.unite(edges[p].u, edges[p].v);
81.       ++p;
82.     }
83.     sol[q.ind] = tree.get_size(q.v) - 1;
84.   }
85.   for (const int &x : sol)
86.     fout << x << '\n';
87. }
88.
89. void close_files() {
90.   fin.close();
91.   fout.close();
92. }
93.
94. int main() {
95.   solve();
96.   close_files();
97.   return 0;
98. }
99.
RAW Paste Data