#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'
const int N = 200200, R = 25025;
int n, r, q, timer=0, tin[N], tout[N];
vector<int> adj[N], color[R];
vector<array<int, 2>> time_in_node[R];
indexed_set<int> time_in[R];
void dfs(int s=0, int e=-1) {
tin[s] = timer++;
for (int node:adj[s]) {
if (node==e) continue;
dfs(node,s);
}
tout[s] = timer;
}
int main() {
scanf("%d%d%d", &n, &r, &q);
int l; scanf("%d", &l); color[l].pb(0);
for (int i=1, s, e;i<=n-1;i++) {
scanf("%d%d", &s, &e);
s--;
adj[s].pb(i), adj[i].pb(s);
color[e].pb(i);
}
dfs();
for (int i = 0; i < R; i++) {
for (int j: color[i]) {
time_in[i].insert(tin[j]);
time_in_node[i].pb({tin[j],j});
}
sort(all(time_in_node[i]));
}
map<pair<int, int>, int> done;
while(q--) {
int i, j; scanf("%d%d", &i, &j);
int ans = 0;
if (done.count({i,j})) { ans = done[{i,j}]; }
else {
int sz = time_in_node[i].size(), k = 0;
while(k < sz) {
int curr_node = time_in_node[i][k][1];
array<int,2> l = {tout[curr_node],0};
int curr = time_in[j].order_of_key(tout[curr_node]) - time_in[j].order_of_key(tin[curr_node]);
assert(curr>=0);
ans += curr;
if (curr == 0) {
k = (upper_bound(all(time_in_node[i]),l) - time_in_node[i].begin());
}
else
k++;
}
done[{i,j}] = ans;
}
printf("%d\n", ans);
fflush(stdout);
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d%d%d", &n, &r, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | int l; scanf("%d", &l); color[l].pb(0);
| ~~~~~^~~~~~~~~~
regions.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d%d", &s, &e);
| ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | int i, j; scanf("%d%d", &i, &j);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8144 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8132 KB |
Output is correct |
| 3 |
Correct |
8 ms |
8144 KB |
Output is correct |
| 4 |
Correct |
14 ms |
8168 KB |
Output is correct |
| 5 |
Correct |
15 ms |
8212 KB |
Output is correct |
| 6 |
Correct |
20 ms |
8288 KB |
Output is correct |
| 7 |
Correct |
41 ms |
8412 KB |
Output is correct |
| 8 |
Correct |
42 ms |
8504 KB |
Output is correct |
| 9 |
Correct |
64 ms |
8992 KB |
Output is correct |
| 10 |
Correct |
120 ms |
9612 KB |
Output is correct |
| 11 |
Correct |
167 ms |
10196 KB |
Output is correct |
| 12 |
Correct |
189 ms |
10972 KB |
Output is correct |
| 13 |
Correct |
304 ms |
11432 KB |
Output is correct |
| 14 |
Correct |
421 ms |
12012 KB |
Output is correct |
| 15 |
Correct |
319 ms |
14480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1533 ms |
17956 KB |
Output is correct |
| 2 |
Correct |
2190 ms |
18104 KB |
Output is correct |
| 3 |
Correct |
2762 ms |
22296 KB |
Output is correct |
| 4 |
Correct |
348 ms |
12888 KB |
Output is correct |
| 5 |
Correct |
356 ms |
14968 KB |
Output is correct |
| 6 |
Correct |
507 ms |
15744 KB |
Output is correct |
| 7 |
Correct |
1000 ms |
16876 KB |
Output is correct |
| 8 |
Correct |
1448 ms |
24884 KB |
Output is correct |
| 9 |
Correct |
3032 ms |
33132 KB |
Output is correct |
| 10 |
Correct |
5773 ms |
39052 KB |
Output is correct |
| 11 |
Execution timed out |
8003 ms |
41544 KB |
Time limit exceeded |
| 12 |
Correct |
3995 ms |
32960 KB |
Output is correct |
| 13 |
Correct |
4304 ms |
35676 KB |
Output is correct |
| 14 |
Correct |
6044 ms |
37876 KB |
Output is correct |
| 15 |
Correct |
7125 ms |
42716 KB |
Output is correct |
| 16 |
Execution timed out |
8061 ms |
44088 KB |
Time limit exceeded |
| 17 |
Execution timed out |
8077 ms |
45004 KB |
Time limit exceeded |
