# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
440792 |
2021-07-03T05:11:27 Z |
zeyu |
Regions (IOI09_regions) |
C++17 |
|
8000 ms |
131076 KB |
#include <bits/stdc++.h>
#define maxn 200020
#define maxm 25025
using namespace std;
vector<int> graph[maxn];
int tin[maxn], tout[maxn];
vector<int> region[maxm];
map<pair<int, int>, int> mp;
int n, q, r, x, y, timer = 0;
struct vertex{
int sum; vertex *l, *r;
vertex(int val){
sum = val; l = 0; r = 0;
}
vertex(vertex *_l, vertex *_r){
l = _l; r = _r;
sum = _l -> sum + _r -> sum;
}
};
struct segtree{
int sz;
vertex* build(int lx, int rx){
if (rx - lx == 1){
return new vertex(0);
}
int mid = (lx + rx) >> 1;
return new vertex(build(lx, mid), build(mid, rx));
}
vertex* build(int n){
sz = n;
return build(0, sz);
}
vertex* set(int i, vertex* v, int lx, int rx){
if (rx - lx == 1){
return new vertex(1);
}
int mid = (lx + rx) >> 1;
if (i < mid) return new vertex(set(i, v -> l, lx, mid), v -> r);
else return new vertex(v -> l, set(i, v -> r, mid, rx));
}
vertex* set(int i, vertex* v){
return set(i, v, 0, sz);
}
int calc(int l, int r, vertex* v, int lx, int rx){
if (lx >= r || rx <= l) return 0;
if (lx >= l && rx <= r) return v -> sum;
int mid = (lx + rx) >> 1;
return calc(l, r, v -> l, lx, mid) + calc(l, r, v -> r, mid, rx);
}
int calc(int l, int r, vertex* v){
return calc(l, r, v, 0, sz);
}
};
void dfs(int x, int p){
tin[x] = timer ++;
for (int i = 0; i < graph[x].size(); i ++){
int to = graph[x][i];
if (to != p) dfs(to, x);
}
tout[x] = timer;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> r >> q;
cin >> x; x --;
region[x].push_back(0);
for (int i = 1; i < n; i ++){
cin >> y >> x;
x --; y --;
region[x].push_back(i);
graph[i].push_back(y);
graph[y].push_back(i);
}
dfs(0, 0);
segtree st;
vector<vertex*> hist;
hist.push_back(st.build(n));
vector<int> sz(r + 1);
for (int i = 1; i <= r; i ++) sz[i] = sz[i - 1] + region[i - 1].size();
for (int i = 0; i < r; i ++){
for (int j = 0; j < region[i].size(); j ++){
hist.push_back(st.set(tin[region[i][j]], hist.back()));
}
}
while(q --){
int r1, r2;
cin >> r1 >> r2;
r1 --; r2 --;
int ans = 0;
if (mp.count(make_pair(r1, r2))){
ans = mp[make_pair(r1, r2)];
} else{
for (int i = 0; i < region[r1].size(); i ++){
int cur = region[r1][i];
ans += st.calc(tin[cur], tout[cur], hist[sz[r2 + 1]]) - st.calc(tin[cur], tout[cur], hist[sz[r2]]);
}
mp[make_pair(r1, r2)] = ans;
}
cout << ans << endl;
}
}
Compilation message
regions.cpp: In function 'void dfs(int, int)':
regions.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < graph[x].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int j = 0; j < region[i].size(); j ++){
| ~~^~~~~~~~~~~~~~~~~~
regions.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i = 0; i < region[r1].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5576 KB |
Output is correct |
2 |
Correct |
6 ms |
5576 KB |
Output is correct |
3 |
Correct |
5 ms |
5576 KB |
Output is correct |
4 |
Correct |
10 ms |
5736 KB |
Output is correct |
5 |
Correct |
18 ms |
5844 KB |
Output is correct |
6 |
Correct |
34 ms |
6108 KB |
Output is correct |
7 |
Correct |
39 ms |
6476 KB |
Output is correct |
8 |
Correct |
63 ms |
6768 KB |
Output is correct |
9 |
Correct |
99 ms |
8784 KB |
Output is correct |
10 |
Correct |
333 ms |
11716 KB |
Output is correct |
11 |
Correct |
809 ms |
14948 KB |
Output is correct |
12 |
Correct |
762 ms |
18504 KB |
Output is correct |
13 |
Correct |
1346 ms |
20984 KB |
Output is correct |
14 |
Correct |
2655 ms |
24848 KB |
Output is correct |
15 |
Correct |
3149 ms |
34216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
8025 ms |
56428 KB |
Time limit exceeded |
2 |
Execution timed out |
8074 ms |
59300 KB |
Time limit exceeded |
3 |
Execution timed out |
8048 ms |
68288 KB |
Time limit exceeded |
4 |
Correct |
2572 ms |
25776 KB |
Output is correct |
5 |
Correct |
2496 ms |
32472 KB |
Output is correct |
6 |
Correct |
3050 ms |
41496 KB |
Output is correct |
7 |
Correct |
2752 ms |
52900 KB |
Output is correct |
8 |
Execution timed out |
8029 ms |
78700 KB |
Time limit exceeded |
9 |
Execution timed out |
8080 ms |
111716 KB |
Time limit exceeded |
10 |
Execution timed out |
8077 ms |
130572 KB |
Time limit exceeded |
11 |
Runtime error |
592 ms |
131076 KB |
Execution killed with signal 9 |
12 |
Runtime error |
499 ms |
131076 KB |
Execution killed with signal 9 |
13 |
Runtime error |
459 ms |
131076 KB |
Execution killed with signal 9 |
14 |
Runtime error |
532 ms |
131076 KB |
Execution killed with signal 9 |
15 |
Runtime error |
474 ms |
131076 KB |
Execution killed with signal 9 |
16 |
Runtime error |
687 ms |
131076 KB |
Execution killed with signal 9 |
17 |
Runtime error |
461 ms |
131076 KB |
Execution killed with signal 9 |