# USACO 2019 December Contest, Silver Problem 3. Milk Visits

Apr 15th, 2021
652
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("milkvisits.in");
6. ofstream fout("milkvisits.out");
7.
8. const int NMAX = 1e5 + 5;
9. int N, Q, level[NMAX], dp[NMAX][2], ancestor[NMAX][18];
10. string s;
11. vector<int> G[NMAX];
12.
13. void dfs(int u, int parent) {
14.   level[u] = level[parent] + 1;
15.   for (int i = 0; i < 2; ++i)
16.     dp[u][i] = dp[parent][i];
17.   if (s[u - 1] == 'G')
18.     ++dp[u][0];
19.   else ++dp[u][1];
20.   ancestor[u][0] = parent;
21.   for (int i = 1; i < 18; ++i)
22.     ancestor[u][i] = ancestor[ancestor[u][i - 1]][i - 1];
23.   for (int v : G[u])
24.     if (v != parent)
25.       dfs(v, u);
26. }
27.
28. int find_lca(int u, int v) {
29.   if (level[u] < level[v])
30.     swap(u, v);
31.   for (int lift = 17; lift >= 0; --lift)
32.     if (level[u] - (1 << lift) >= level[v])
33.       u = ancestor[u][lift];
34.   if (u == v)
35.     return u;
36.   for (int lift = 17; lift >= 0; --lift)
37.     if (ancestor[u][lift] != ancestor[v][lift]) {
38.       u = ancestor[u][lift];
39.       v = ancestor[v][lift];
40.     }
41.   return ancestor[u][0];
42. }
43.
44. void solve() {
45.   fin >> N >> Q >> s;
46.   for (int i = 1; i < N; ++i) {
47.     int u, v;
48.     fin >> u >> v;
49.     G[u].emplace_back(v);
50.     G[v].emplace_back(u);
51.   }
52.   dfs(1, 0);
53.   for (int q = 0; q < Q; ++q) {
54.     int u, v;
55.     char req;
56.     fin >> u >> v >> req;
57.     int lca = find_lca(u, v), type;
58.     if (req == 'G')
59.       type = 0;
60.     else type = 1;
61.     if (dp[u][type] + dp[v][type] - (dp[lca][type] << 1) + (s[lca - 1] == req) > 0)
62.       fout << '1';
63.     else fout << '0';
64.   }
65. }
66.
67. void close_files() {
68.   fin.close();
69.   fout.close();
70. }
71.
72. int main() {
73.   solve();
74.   close_files();
75.   return 0;
76. }
77.
RAW Paste Data