| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291843 |
2020-09-05T20:54:05 Z |
evpipis |
Regions (IOI09_regions) |
C++11 |
|
3742 ms |
45816 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int len = 2e5+5, len_reg = 25005, len_k = 455;
int temp_val[len], reg[len], st[len], en[len], order[len], par[len], pos[len], cnt;
int prec1[len_k][len_reg], prec2[len_k][len_reg];
vector<int> adj[len], tree[len];
void fix(int u){
st[u] = ++cnt;
order[cnt] = u;
tree[reg[u]].pb(u);
for (auto v: adj[u])
fix(v);
en[u] = cnt;
}
bool is_anc(int u, int v){
return (st[u] <= st[v] && en[v] <= en[u]);
}
int brute(vector<int> &fir, vector<int> &sec){
int ans = 0;
vector<int> stck(1, 0);
for (int i = 0, j = 0; i < fir.size() || j < sec.size(); ){
int u, tp;
if (i == fir.size())
u = sec[j++], tp = 2;
else if (j == sec.size())
u = fir[i++], tp = 1;
else if (st[fir[i]] < st[sec[j]])
u = fir[i++], tp = 1;
else
u = sec[j++], tp = 2;
while (!is_anc(stck.back(), u))
stck.pop_back();
temp_val[u] = temp_val[stck.back()];
stck.pb(u);
if (tp == 1)
temp_val[u]++;
else
ans += temp_val[u];
//printf("u = %d, temp_val = %d\n", u, temp_val[u]);
}
return ans;
}
int dfs(int u, int big, int many){
if (reg[u] == big) many++;
else prec1[pos[big]][reg[u]] += many;
int ans = 0;
for (auto v: adj[u])
ans += dfs(v, big, many);
if (reg[u] == big) ans++;
else prec2[pos[big]][reg[u]] += ans;
return ans;
}
int main(){
int n, r, q;
scanf("%d %d %d", &n, &r, &q);
scanf("%d", ®[1]);
for (int i = 2; i <= n; i++){
scanf("%d %d", &par[i], ®[i]);
adj[par[i]].pb(i);
}
fix(1);
st[0] = 0, en[0] = n;
int k = sqrt(n);
for (int i = 1, j = 0; i <= r; i++)
if (tree[i].size() > k)
pos[i] = j++, dfs(1, i, 0);
while (q--){
int r1, r2;
scanf("%d %d", &r1, &r2);
if (tree[r1].size() > k)
printf("%d\n", prec1[pos[r1]][r2]);
else if (tree[r2].size() > k)
printf("%d\n", prec2[pos[r2]][r1]);
else
printf("%d\n", brute(tree[r1], tree[r2]));
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp: In function 'int brute(std::vector<int>&, std::vector<int>&)':
regions.cpp:30:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0, j = 0; i < fir.size() || j < sec.size(); ){
| ~~^~~~~~~~~~~~
regions.cpp:30:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0, j = 0; i < fir.size() || j < sec.size(); ){
| ~~^~~~~~~~~~~~
regions.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | if (i == fir.size())
| ~~^~~~~~~~~~~~~
regions.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | else if (j == sec.size())
| ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:84:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | if (tree[i].size() > k)
| ~~~~~~~~~~~~~~~^~~
regions.cpp:90:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
90 | if (tree[r1].size() > k)
| ~~~~~~~~~~~~~~~~^~~
regions.cpp:92:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
92 | else if (tree[r2].size() > k)
| ~~~~~~~~~~~~~~~~^~~
regions.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
72 | scanf("%d %d %d", &n, &r, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d", ®[1]);
| ~~~~~^~~~~~~~~~~~~~~
regions.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d %d", &par[i], ®[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
89 | scanf("%d %d", &r1, &r2);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 5 |
Correct |
17 ms |
9728 KB |
Output is correct |
| 6 |
Correct |
27 ms |
9856 KB |
Output is correct |
| 7 |
Correct |
40 ms |
9856 KB |
Output is correct |
| 8 |
Correct |
41 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
48 ms |
10240 KB |
Output is correct |
| 10 |
Correct |
112 ms |
10368 KB |
Output is correct |
| 11 |
Correct |
156 ms |
10752 KB |
Output is correct |
| 12 |
Correct |
187 ms |
11136 KB |
Output is correct |
| 13 |
Correct |
173 ms |
10880 KB |
Output is correct |
| 14 |
Correct |
253 ms |
11640 KB |
Output is correct |
| 15 |
Correct |
246 ms |
14780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1076 ms |
15372 KB |
Output is correct |
| 2 |
Correct |
1265 ms |
13816 KB |
Output is correct |
| 3 |
Correct |
2445 ms |
17400 KB |
Output is correct |
| 4 |
Correct |
350 ms |
11512 KB |
Output is correct |
| 5 |
Correct |
410 ms |
13184 KB |
Output is correct |
| 6 |
Correct |
662 ms |
16728 KB |
Output is correct |
| 7 |
Correct |
1082 ms |
18424 KB |
Output is correct |
| 8 |
Correct |
1126 ms |
28920 KB |
Output is correct |
| 9 |
Correct |
2455 ms |
19704 KB |
Output is correct |
| 10 |
Correct |
2476 ms |
45816 KB |
Output is correct |
| 11 |
Correct |
3742 ms |
19832 KB |
Output is correct |
| 12 |
Correct |
1404 ms |
21752 KB |
Output is correct |
| 13 |
Correct |
1986 ms |
22136 KB |
Output is correct |
| 14 |
Correct |
2412 ms |
25344 KB |
Output is correct |
| 15 |
Correct |
3262 ms |
27156 KB |
Output is correct |
| 16 |
Correct |
3425 ms |
34428 KB |
Output is correct |
| 17 |
Correct |
3278 ms |
36344 KB |
Output is correct |
