# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
909105 |
2024-01-17T05:19:36 Z |
anarch_y |
Regions (IOI09_regions) |
C++17 |
|
8000 ms |
23672 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 st[maxn], en[maxn];
int timer = 0;
void dfs(int s, int p){
st[s] = timer++;
for(auto u: adj[s]){
if(u == p) continue;
dfs(u, s);
}
en[s] = timer;
}
bool anc(int a, int b){
return st[a] <= st[b] and en[b] <= en[a];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N, R, Q; cin >> N >> R >> Q;
vector<int> reg[R+1];
int h; cin >> h;
reg[h].pb(1);
for(int i=2; i<=N; i++){
int p, r; cin >> p >> r;
adj[i].pb(p); adj[p].pb(i);
reg[r].pb(i);
}
dfs(1, 0);
while(Q--){
int r1, r2; cin >> r1 >> r2;
int ans = 0;
for(auto a: reg[r1]){
for(auto b: reg[r2]){
if(anc(a, b)) ans++;
}
}
cout << ans << "\n";
cout.flush();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6488 KB |
Output is correct |
2 |
Correct |
2 ms |
6488 KB |
Output is correct |
3 |
Correct |
5 ms |
6488 KB |
Output is correct |
4 |
Correct |
4 ms |
6488 KB |
Output is correct |
5 |
Correct |
5 ms |
6488 KB |
Output is correct |
6 |
Correct |
10 ms |
6488 KB |
Output is correct |
7 |
Correct |
18 ms |
6488 KB |
Output is correct |
8 |
Correct |
21 ms |
6488 KB |
Output is correct |
9 |
Correct |
31 ms |
7000 KB |
Output is correct |
10 |
Correct |
53 ms |
7000 KB |
Output is correct |
11 |
Correct |
122 ms |
7000 KB |
Output is correct |
12 |
Correct |
133 ms |
7668 KB |
Output is correct |
13 |
Correct |
242 ms |
7512 KB |
Output is correct |
14 |
Correct |
621 ms |
7768 KB |
Output is correct |
15 |
Correct |
576 ms |
9856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
8085 ms |
10004 KB |
Time limit exceeded |
2 |
Execution timed out |
8005 ms |
9616 KB |
Time limit exceeded |
3 |
Execution timed out |
8086 ms |
11372 KB |
Time limit exceeded |
4 |
Correct |
189 ms |
8024 KB |
Output is correct |
5 |
Correct |
262 ms |
9304 KB |
Output is correct |
6 |
Correct |
7901 ms |
9040 KB |
Output is correct |
7 |
Correct |
4238 ms |
9844 KB |
Output is correct |
8 |
Correct |
2497 ms |
13836 KB |
Output is correct |
9 |
Correct |
4066 ms |
13708 KB |
Output is correct |
10 |
Execution timed out |
8021 ms |
18232 KB |
Time limit exceeded |
11 |
Execution timed out |
8055 ms |
15396 KB |
Time limit exceeded |
12 |
Execution timed out |
8079 ms |
14232 KB |
Time limit exceeded |
13 |
Execution timed out |
8064 ms |
15092 KB |
Time limit exceeded |
14 |
Execution timed out |
8079 ms |
15212 KB |
Time limit exceeded |
15 |
Execution timed out |
8052 ms |
18216 KB |
Time limit exceeded |
16 |
Execution timed out |
8038 ms |
23672 KB |
Time limit exceeded |
17 |
Execution timed out |
8010 ms |
22564 KB |
Time limit exceeded |