# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
298964 |
2020-09-14T11:17:53 Z |
jovan_b |
Regions (IOI09_regions) |
C++17 |
|
4347 ms |
30092 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int LIM = 50000000;
int in[200005];
int out[200005];
int region[200005];
int parent[200005];
int cnt[200005];
vector <int> graf[200005];
int gore[25005][505];
int dole[25005][505];
int sada[25005];
int rev[25005];
int compress[25005];
int ccomp;
int r;
int tajm;
vector <pair <int, int>> svi[25005];
vector <int> ins[25005];
void dfs(int v){
in[v] = ++tajm;
sada[region[v]]++;
if(compress[region[v]]){
for(int i=1; i<=r; i++){
dole[i][compress[region[v]]] += sada[region[v]];
}
dole[region[v]][compress[region[v]]]--;
gore[region[v]][compress[region[v]]]--;
}
for(int i=1; i<=ccomp; i++){
gore[region[v]][i] += sada[rev[i]];
}
for(auto c : graf[v]){
dfs(c);
}
sada[region[v]]--;
out[v] = tajm;
svi[region[v]].push_back({in[v], 1});
svi[region[v]].push_back({out[v]+1, -1});
ins[region[v]].push_back(in[v]);
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
int n, q;
cin >> n >> r >> q;
cin >> region[1];
cnt[region[1]]++;
for(int i=2; i<=n; i++){
cin >> parent[i] >> region[i];
cnt[region[i]]++;
graf[parent[i]].push_back(i);
}
for(int i=1; i<=r; i++){
if(cnt[i] <= LIM) continue;
compress[i] = ++ccomp;
rev[ccomp] = i;
}
dfs(1);
for(int i=1; i<=r; i++) sort(svi[i].begin(), svi[i].end());
for(int i=1; i<=r; i++) sort(ins[i].begin(), ins[i].end());
while(q--){
int a, b;
cin >> a >> b;
if(cnt[a] > LIM){
cout << gore[b][compress[a]] << endl;
continue;
}
if(cnt[b] > LIM){
cout << dole[a][compress[b]] << endl;
continue;
}
int k = svi[a].size();
int j = -1;
int tren = 0;
ll res = 0;
for(auto c : ins[b]){
while(j < k-1 && c >= svi[a][j+1].first){
j++;
tren += svi[a][j].second;
}
res += tren;
}
cout << res << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6272 KB |
Output is correct |
2 |
Correct |
4 ms |
6272 KB |
Output is correct |
3 |
Correct |
5 ms |
6272 KB |
Output is correct |
4 |
Correct |
8 ms |
6272 KB |
Output is correct |
5 |
Correct |
9 ms |
6272 KB |
Output is correct |
6 |
Correct |
24 ms |
6400 KB |
Output is correct |
7 |
Correct |
25 ms |
6400 KB |
Output is correct |
8 |
Correct |
31 ms |
6400 KB |
Output is correct |
9 |
Correct |
45 ms |
6912 KB |
Output is correct |
10 |
Correct |
70 ms |
7040 KB |
Output is correct |
11 |
Correct |
110 ms |
7424 KB |
Output is correct |
12 |
Correct |
128 ms |
8112 KB |
Output is correct |
13 |
Correct |
146 ms |
7936 KB |
Output is correct |
14 |
Correct |
190 ms |
8704 KB |
Output is correct |
15 |
Correct |
222 ms |
11384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2606 ms |
12308 KB |
Output is correct |
2 |
Correct |
3993 ms |
11428 KB |
Output is correct |
3 |
Correct |
3836 ms |
14468 KB |
Output is correct |
4 |
Correct |
304 ms |
8764 KB |
Output is correct |
5 |
Correct |
497 ms |
10340 KB |
Output is correct |
6 |
Correct |
893 ms |
10180 KB |
Output is correct |
7 |
Correct |
881 ms |
11760 KB |
Output is correct |
8 |
Correct |
1078 ms |
16992 KB |
Output is correct |
9 |
Correct |
1520 ms |
19320 KB |
Output is correct |
10 |
Correct |
2325 ms |
23672 KB |
Output is correct |
11 |
Correct |
2496 ms |
19904 KB |
Output is correct |
12 |
Correct |
1967 ms |
20720 KB |
Output is correct |
13 |
Correct |
2148 ms |
20892 KB |
Output is correct |
14 |
Correct |
2877 ms |
20840 KB |
Output is correct |
15 |
Correct |
3616 ms |
25200 KB |
Output is correct |
16 |
Correct |
3497 ms |
30092 KB |
Output is correct |
17 |
Correct |
4347 ms |
29352 KB |
Output is correct |