| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 908483 |
2024-01-16T12:48:41 Z |
anarch_y |
Regions (IOI09_regions) |
C++17 |
|
2142 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
const int maxn = 200001;
vector<int> adj[maxn];
int home[maxn];
map<int, int> mp[maxn];
map<pair<int, int>, int> ans;
void dfs(int s, int p){
mp[s][home[s]] = 1;
for(auto u: adj[s]){
if(u == p) continue;
dfs(u, s);
if(sz(mp[s]) < sz(mp[u])) swap(mp[u], mp[s]);
for(auto &[r, m]: mp[u]) mp[s][r] += m;
mp[u].clear();
}
for(auto &[r, m]: mp[s]){
if(r == home[s]){
ans[{r, r}] += m-1;
}
else{
ans[{home[s], r}] += m;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N, R, Q; cin >> N >> R >> Q;
int h; cin >> h; home[1] = h;
for(int i=2; i<=N; i++){
int p, g; cin >> p >> g;
adj[i].pb(p); adj[p].pb(i);
home[i] = g;
}
dfs(1, 0);
while(Q--){
int r1, r2; cin >> r1 >> r2;
cout << ans[{r1, r2}] << "\n";
cout.flush();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
15444 KB |
Output is correct |
| 2 |
Correct |
5 ms |
15192 KB |
Output is correct |
| 3 |
Correct |
5 ms |
15340 KB |
Output is correct |
| 4 |
Correct |
9 ms |
15620 KB |
Output is correct |
| 5 |
Correct |
9 ms |
15448 KB |
Output is correct |
| 6 |
Correct |
33 ms |
18980 KB |
Output is correct |
| 7 |
Correct |
22 ms |
16880 KB |
Output is correct |
| 8 |
Correct |
32 ms |
17976 KB |
Output is correct |
| 9 |
Correct |
153 ms |
21840 KB |
Output is correct |
| 10 |
Correct |
97 ms |
24352 KB |
Output is correct |
| 11 |
Correct |
133 ms |
20460 KB |
Output is correct |
| 12 |
Correct |
540 ms |
29428 KB |
Output is correct |
| 13 |
Correct |
134 ms |
22608 KB |
Output is correct |
| 14 |
Correct |
154 ms |
18996 KB |
Output is correct |
| 15 |
Correct |
815 ms |
28452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1149 ms |
23240 KB |
Output is correct |
| 2 |
Correct |
616 ms |
21340 KB |
Output is correct |
| 3 |
Correct |
2142 ms |
29760 KB |
Output is correct |
| 4 |
Runtime error |
598 ms |
131072 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
679 ms |
131072 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
587 ms |
131072 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
489 ms |
131072 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
691 ms |
131072 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
459 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
714 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
545 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
785 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
614 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
631 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
499 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
394 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
534 ms |
131072 KB |
Execution killed with signal 9 |
