# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
763780 |
2023-06-22T20:59:45 Z |
izanbf |
Regions (IOI09_regions) |
C++14 |
|
5290 ms |
110460 KB |
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int BIG = 300;
vi r, tin, tout, big_id;
vvi adj, tins, touts, by_r, dp;
int timer;
void euler(int u, int p) {
tin[u] = timer++;
tins[r[u]].push_back(tin[u]);
for (int v : adj[u]) {
if (v != p) euler(v, u);
}
tout[u] = timer++;
touts[r[u]].push_back(tout[u]);
}
int count_in_range(const vi& v, int l, int r) {
if (v.empty()) return 0;
int ri = upper_bound(v.begin(), v.end(), r) - v.begin();
int li = upper_bound(v.begin(), v.end(), l) - v.begin();
return ri - li;
}
void precompute(int rg, int p, int u) {
int rid = big_id[rg];
dp[rid][u] = (r[u] == rg);
for (int v : adj[u]) {
if (v != p) {
precompute(rg, u, v);
dp[rid][u] += dp[rid][v];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, R, Q;
cin >> N >> R >> Q;
r = tin = tout = vi(N);
big_id = vi(R);
adj = vvi(N);
tins = touts = by_r = vvi(R);
vi p(N, -1);
cin >> r[0]; --r[0];
by_r[r[0]].push_back(0);
for (int i = 1; i < N; ++i) {
cin >> p[i] >> r[i]; --p[i], --r[i];
by_r[r[i]].push_back(i);
adj[i].push_back(p[i]);
adj[p[i]].push_back(i);
}
int bigs = 0;
for (int rg = 0; rg < R; ++rg) {
if (by_r[rg].size() >= BIG) big_id[rg] = bigs++;
}
dp = vvi(bigs, vi(N)); // O(N/BIG N)
for (int rg = 0; rg < R; ++rg) {
if (by_r[rg].size() >= BIG) precompute(rg, 0, 0);
}
timer = 1;
euler(0, 0);
map<pair<int,int>,long long> mem;
while (Q--) {
int r1, r2;
cin >> r1 >> r2; --r1, --r2;
if (by_r[r1].size() < BIG and by_r[r2].size() >= BIG) { // r1 small r2 big O(Q BIG)
long long cnt = 0;
int rid = big_id[r2];
for (int u : by_r[r1]) {
cnt += dp[rid][u];
}
cout << cnt << endl;
}
else { //O(Q BIG log N)
if (not mem.count({r1,r2})) {
long long cnt = 0;
for (int u : by_r[r2]) {
cnt += count_in_range(tins[r1], 0, tin[u])
- count_in_range(touts[r1], 0, tin[u]);
}
mem[{r1,r2}] = cnt;
}
cout << mem[{r1,r2}] << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
3 ms |
208 KB |
Output is correct |
4 |
Correct |
3 ms |
336 KB |
Output is correct |
5 |
Correct |
6 ms |
336 KB |
Output is correct |
6 |
Correct |
19 ms |
464 KB |
Output is correct |
7 |
Correct |
29 ms |
560 KB |
Output is correct |
8 |
Correct |
33 ms |
636 KB |
Output is correct |
9 |
Correct |
32 ms |
1416 KB |
Output is correct |
10 |
Correct |
81 ms |
1712 KB |
Output is correct |
11 |
Correct |
101 ms |
2232 KB |
Output is correct |
12 |
Correct |
143 ms |
3076 KB |
Output is correct |
13 |
Correct |
165 ms |
3240 KB |
Output is correct |
14 |
Correct |
241 ms |
3900 KB |
Output is correct |
15 |
Correct |
205 ms |
7408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1088 ms |
16320 KB |
Output is correct |
2 |
Correct |
1388 ms |
13272 KB |
Output is correct |
3 |
Correct |
1760 ms |
18288 KB |
Output is correct |
4 |
Correct |
259 ms |
5376 KB |
Output is correct |
5 |
Correct |
358 ms |
7764 KB |
Output is correct |
6 |
Correct |
579 ms |
20140 KB |
Output is correct |
7 |
Correct |
695 ms |
23136 KB |
Output is correct |
8 |
Correct |
1016 ms |
57832 KB |
Output is correct |
9 |
Correct |
2228 ms |
54572 KB |
Output is correct |
10 |
Correct |
3534 ms |
100000 KB |
Output is correct |
11 |
Correct |
5290 ms |
110460 KB |
Output is correct |
12 |
Correct |
1398 ms |
24092 KB |
Output is correct |
13 |
Correct |
1978 ms |
27208 KB |
Output is correct |
14 |
Correct |
2340 ms |
44416 KB |
Output is correct |
15 |
Correct |
3003 ms |
37356 KB |
Output is correct |
16 |
Correct |
2901 ms |
46340 KB |
Output is correct |
17 |
Correct |
2813 ms |
60012 KB |
Output is correct |