# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1026965 |
2024-07-18T15:28:27 Z |
daisy2 |
Regions (IOI09_regions) |
C++17 |
|
8000 ms |
131072 KB |
#include<bits/stdc++.h>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
int n, chair, q, tim = 0, in[200005], out[200005], rper[200005], reg, a, b;
vector<int> v[200005], perr[200005];
map<int, int> dp[25000];
multiset<int> d[500005];
void dfs(int vr) {
tim++;
in[vr] = tim;
d[rper[vr]].insert(in[vr]);
for (int i = 0; i < v[vr].size(); i++)
dfs(v[vr][i]);
out[vr] = tim;
}
void dfs2(int vr, int cntim, int curr) {
if (rper[vr] == curr) cntim++;
else dp[curr][rper[vr]] += cntim;
for (int i = 0; i < v[vr].size(); i++)
dfs2(v[vr][i], cntim, curr);
}
int main() {
cin >> n >> reg >> q;
cin >> chair;
rper[1] = chair;
perr[chair].push_back(1);
int sup, regper;
for (int i = 2; i <= n; i++) {
cin >> sup >> regper;
v[sup].push_back(i);
rper[i] = regper;
perr[regper].push_back(i);
}
dfs(1);
int k = sqrt(n);
for (int i = 1; i <= reg; i++) {
if (d[i].size() >= k) {
dfs2(1, 0, i);
}
}
while (q--) {
cin >> a >> b;
if (d[a].size() >= k) {
cout << dp[a][b] << endl;
} else {
int res = 0;
for (int i = 0; i < perr[a].size(); i++) {
res += distance(d[b].lower_bound(in[perr[a][i]]), d[b].upper_bound(out[perr[a][i]]));
}
cout << res << endl;
}
cout.flush();
}
}
Compilation message
regions.cpp: In function 'void dfs(int)':
regions.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < v[vr].size(); i++)
| ~~^~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(int, int, int)':
regions.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int i = 0; i < v[vr].size(); i++)
| ~~^~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | if (d[i].size() >= k) {
| ~~~~~~~~~~~~^~~~
regions.cpp:55:25: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if (d[a].size() >= k) {
| ~~~~~~~~~~~~^~~~
regions.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < perr[a].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
35416 KB |
Output is correct |
2 |
Correct |
5 ms |
35416 KB |
Output is correct |
3 |
Correct |
6 ms |
35416 KB |
Output is correct |
4 |
Correct |
7 ms |
35456 KB |
Output is correct |
5 |
Correct |
10 ms |
35416 KB |
Output is correct |
6 |
Correct |
15 ms |
35416 KB |
Output is correct |
7 |
Correct |
19 ms |
35416 KB |
Output is correct |
8 |
Correct |
23 ms |
35672 KB |
Output is correct |
9 |
Correct |
38 ms |
36184 KB |
Output is correct |
10 |
Correct |
67 ms |
36184 KB |
Output is correct |
11 |
Correct |
120 ms |
36696 KB |
Output is correct |
12 |
Correct |
116 ms |
37464 KB |
Output is correct |
13 |
Correct |
152 ms |
37208 KB |
Output is correct |
14 |
Correct |
261 ms |
37976 KB |
Output is correct |
15 |
Correct |
1445 ms |
42024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
8047 ms |
43344 KB |
Time limit exceeded |
2 |
Execution timed out |
8063 ms |
41808 KB |
Time limit exceeded |
3 |
Execution timed out |
8031 ms |
46160 KB |
Time limit exceeded |
4 |
Correct |
188 ms |
37976 KB |
Output is correct |
5 |
Correct |
306 ms |
40536 KB |
Output is correct |
6 |
Correct |
714 ms |
57424 KB |
Output is correct |
7 |
Correct |
1670 ms |
65196 KB |
Output is correct |
8 |
Correct |
2900 ms |
96848 KB |
Output is correct |
9 |
Correct |
2810 ms |
50404 KB |
Output is correct |
10 |
Runtime error |
1081 ms |
131072 KB |
Execution killed with signal 9 |
11 |
Correct |
4690 ms |
51540 KB |
Output is correct |
12 |
Correct |
2474 ms |
54096 KB |
Output is correct |
13 |
Correct |
6938 ms |
54864 KB |
Output is correct |
14 |
Correct |
6432 ms |
70984 KB |
Output is correct |
15 |
Execution timed out |
8023 ms |
61548 KB |
Time limit exceeded |
16 |
Execution timed out |
8018 ms |
70984 KB |
Time limit exceeded |
17 |
Execution timed out |
8026 ms |
85696 KB |
Time limit exceeded |