# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
870887 |
2023-11-09T11:49:58 Z |
rsjw |
Regions (IOI09_regions) |
C++17 |
|
46 ms |
19824 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int R = 25005;
int h[N];
int threshold;
struct edge {
int to;
edge *nex;
} * head[N];
void add(int u, int v) {
edge *cur = new edge;
cur->to = v;
cur->nex = head[u];
head[u] = cur;
}
struct query {
int a, b;
} q[N];
int cnt[R];
vector<int> _sub[R], _top[R];
map<int, int> sub[R], top[R];
map<int, int> s;
void dfs1(int u, int fa) {
for (auto x : _top[h[u]])
top[h[u]][x] += s[x];
s[h[u]]++;
for (edge *cur = head[u]; cur; cur = cur->nex) {
if (cur->to == fa)
continue;
dfs1(cur->to, u);
}
if (s[h[u]] == 1)
s.erase(h[u]);
else
s[h[u]]--;
}
map<int, int> dfs2(int u, int fa) {
map<int, int> s1, s2;
for (edge *cur = head[u]; cur; cur = cur->nex) {
if (cur->to == fa)
continue;
s2 = dfs2(cur->to, u);
if (s2.size() > s1.size())
swap(s1, s2);
for (auto x : s2)
s1[x.first] += x.second;
}
for (auto x : _sub[h[u]]) {
if (s1.find(x) != s1.end())
sub[h[u]][x] += s1[x];
}
s1[h[u]]++;
return s1;
}
void get() {
int n, m, t, i, x;
cin >> n >> m >> t >> h[1];
cnt[h[1]]++;
for (i = 2; i <= n; i++) {
cin >> x >> h[i];
cnt[h[i]]++;
add(x, i);
add(i, x);
}
threshold = sqrt(n);
for (i = 1; i <= t; i++) {
cin >> q[i].a >> q[i].b;
if (cnt[q[i].b] >= threshold) {
_sub[q[i].a].push_back(q[i].b);
} else {
_top[q[i].b].push_back(q[i].a);
}
}
for (i = 1; i <= m; i++) {
sort(_sub[i].begin(), _sub[i].end());
_sub[i].erase(unique(_sub[i].begin(), _sub[i].end()), _sub[i].end());
sort(_top[i].begin(), _top[i].end());
_top[i].erase(unique(_top[i].begin(), _top[i].end()), _top[i].end());
}
dfs1(1, 0);
dfs2(1, 0);
for (i = 1; i <= t; i++) {
if (cnt[q[i].b] >= threshold) {
cout << sub[q[i].a][q[i].b] << endl;
} else {
cout << top[q[i].b][q[i].a] << endl;
}
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
get();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1 ms |
4948 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
1 ms |
4696 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
1 ms |
4696 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
1 ms |
4696 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
1 ms |
4696 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
1 ms |
4696 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
2 ms |
4696 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
1 ms |
4696 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
2 ms |
4952 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
3 ms |
5464 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
4 ms |
5720 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
7 ms |
5976 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
5 ms |
6492 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
6 ms |
6764 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
7 ms |
7532 KB |
Time limit exceeded (wall clock) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
15 ms |
10256 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
14 ms |
10532 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
18 ms |
11380 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
6 ms |
6744 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
8 ms |
7256 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
10 ms |
8488 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
15 ms |
9800 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
18 ms |
12224 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
37 ms |
15816 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
31 ms |
17420 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
40 ms |
19716 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
39 ms |
18736 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
35 ms |
18808 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
46 ms |
19692 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
37 ms |
19712 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
45 ms |
19824 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
46 ms |
19540 KB |
Time limit exceeded (wall clock) |