# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
265273 |
2020-08-14T14:40:51 Z |
WLZ |
Regions (IOI09_regions) |
C++14 |
|
8000 ms |
29284 KB |
#include <bits/stdc++.h>
using namespace std;
int n, r, q, cur = 0;
vector<int> h, s;
vector< vector<int> > g;
vector< vector< pair<int, int> > > reg;
int dfs(int u) {
int st = cur++;
int en = st;
for (auto& v : g[u]) {
en = dfs(v);
}
reg[h[u]].push_back({st, 1});
reg[h[u]].push_back({en, -1});
return en;
}
long long solve(int r1, int r2) {
int cur = 0, idx = -1;
long long ans = 0;
for (auto& p : reg[r2]) {
if (p.second == -1) {
continue;
}
while (idx + 1 < (int) reg[r1].size() && reg[r1][idx + 1].first < p.first) {
idx++;
cur += reg[r1][idx].second;
}
ans += (long long) cur;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> r >> q;
h.resize(n + 1);
s.resize(n + 1);
cin >> h[1];
g.resize(n + 1);
for (int i = 2; i <= n; i++) {
cin >> s[i] >> h[i];
g[s[i]].push_back(i);
}
reg.resize(r + 1);
dfs(1);
for (int i = 1; i <= r; i++) {
sort(reg[i].begin(), reg[i].end());
}
while (q--) {
int r1, r2;
cin >> r1 >> r2;
cout << solve(r1, r2) << endl;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
7 ms |
384 KB |
Output is correct |
6 |
Correct |
17 ms |
512 KB |
Output is correct |
7 |
Correct |
27 ms |
640 KB |
Output is correct |
8 |
Correct |
30 ms |
512 KB |
Output is correct |
9 |
Correct |
44 ms |
1280 KB |
Output is correct |
10 |
Correct |
75 ms |
1276 KB |
Output is correct |
11 |
Correct |
108 ms |
1664 KB |
Output is correct |
12 |
Correct |
131 ms |
2552 KB |
Output is correct |
13 |
Correct |
125 ms |
2296 KB |
Output is correct |
14 |
Correct |
195 ms |
2944 KB |
Output is correct |
15 |
Correct |
226 ms |
6400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3974 ms |
7412 KB |
Output is correct |
2 |
Execution timed out |
8031 ms |
6264 KB |
Time limit exceeded |
3 |
Correct |
5044 ms |
9972 KB |
Output is correct |
4 |
Correct |
231 ms |
3168 KB |
Output is correct |
5 |
Correct |
367 ms |
5248 KB |
Output is correct |
6 |
Correct |
834 ms |
4984 KB |
Output is correct |
7 |
Correct |
1190 ms |
6652 KB |
Output is correct |
8 |
Correct |
949 ms |
13184 KB |
Output is correct |
9 |
Correct |
1758 ms |
15096 KB |
Output is correct |
10 |
Correct |
2426 ms |
20936 KB |
Output is correct |
11 |
Correct |
3148 ms |
16032 KB |
Output is correct |
12 |
Correct |
4343 ms |
16624 KB |
Output is correct |
13 |
Correct |
5023 ms |
17136 KB |
Output is correct |
14 |
Correct |
7390 ms |
17132 KB |
Output is correct |
15 |
Correct |
4970 ms |
22256 KB |
Output is correct |
16 |
Correct |
4590 ms |
29284 KB |
Output is correct |
17 |
Correct |
5298 ms |
28012 KB |
Output is correct |