# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
794588 |
2023-07-26T15:56:36 Z |
Cookie |
Regions (IOI09_regions) |
C++14 |
|
3653 ms |
131072 KB |
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const ll mod = 1e9 + 7;
const int mxn = 5e5 + 5, mxm = 1e5, sq = 800;
const ld inf = 1e9;
int n, r, q, root;
int colour[mxn + 1], tin[mxn + 1], tout[mxn + 1], tt = 0, cnt[mxn + 1];
vt<int>vec[mxn + 1], adj[mxn + 1], to[mxn + 1];
vt<ll>ansb[mxn + 1];
void dfs(int s, int pre){
tin[s] = ++tt;
for(auto i: adj[s]){
if(i != pre){
dfs(i, s);
}
}
tout[s] = tt;
}
struct th{
int id, pos, type;
bool operator <(const th &b){
if(pos != b.pos)return(pos < b.pos);
if(type != b.type)return(type < b.type);
return(id > b.id);
}
};
void solvebig(int i){
vt<th>comp;
for(auto k: vec[i]){
comp.pb({0, tin[k], -1}); comp.pb({0, tout[k],1});
}
for(int j = 1; j <= r; j++){
if(j != i){
for(auto k: vec[j]){
comp.pb({k, tin[k], -1}); comp.pb({k, tout[k], 1});
}
}
}
sort(comp.begin(), comp.end());
ll cnt =0 ;
for(auto [id, pos, type]: comp){
if(id == 0){
if(type == 1)cnt++;
else cnt--;
}else{
if(type == 1)ansb[i][id] -= cnt;
else ansb[i][id] += cnt;
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> r >> q;
cin >> colour[1];
vec[colour[1]].pb(1);
for(int i = 2; i <= n; i++){
int p;
cin >> p >> colour[i]; cnt[colour[i]]++;
vec[colour[i]].pb(i); adj[p].pb(i);
}
dfs(1, -1);
for(int i = 1; i <= r; i++){
for(auto j: vec[i]){
to[i].pb(tin[j]);
}
sort(to[i].begin(), to[i].end());
}
for(int i = 1; i <= r; i++){
if(cnt[i] >= sq){
ansb[i].resize(r + 1);
solvebig(i);
}
}
while(q--){
int r1, r2; cin >> r1 >> r2;
if(cnt[r1] >= sq){
cout << ansb[r1][r2] << endl;
}else{
ll ans = 0;
for(auto i: vec[r1]){
int idl = lower_bound(to[r2].begin(), to[r2].end(), tin[i]) - to[r2].begin();
int idr = upper_bound(to[r2].begin(), to[r2].end(), tout[i]) - to[r2].begin() - 1;
ans += 1LL * (idr - idl + 1);
}
cout << ans << endl;
}
}
return(0);
}
Compilation message
regions.cpp: In function 'void solvebig(int)':
regions.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for(auto [id, pos, type]: comp){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
47240 KB |
Output is correct |
2 |
Correct |
22 ms |
47204 KB |
Output is correct |
3 |
Correct |
23 ms |
47268 KB |
Output is correct |
4 |
Correct |
26 ms |
47312 KB |
Output is correct |
5 |
Correct |
29 ms |
47312 KB |
Output is correct |
6 |
Correct |
33 ms |
47332 KB |
Output is correct |
7 |
Correct |
49 ms |
47312 KB |
Output is correct |
8 |
Correct |
40 ms |
47344 KB |
Output is correct |
9 |
Correct |
52 ms |
47732 KB |
Output is correct |
10 |
Correct |
80 ms |
47816 KB |
Output is correct |
11 |
Correct |
103 ms |
48092 KB |
Output is correct |
12 |
Correct |
114 ms |
48544 KB |
Output is correct |
13 |
Correct |
189 ms |
48272 KB |
Output is correct |
14 |
Correct |
236 ms |
48752 KB |
Output is correct |
15 |
Correct |
179 ms |
51408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
96 ms |
108888 KB |
Execution killed with signal 11 |
2 |
Runtime error |
104 ms |
106736 KB |
Execution killed with signal 11 |
3 |
Runtime error |
112 ms |
113220 KB |
Execution killed with signal 11 |
4 |
Correct |
276 ms |
48932 KB |
Output is correct |
5 |
Correct |
279 ms |
50504 KB |
Output is correct |
6 |
Correct |
1069 ms |
50120 KB |
Output is correct |
7 |
Correct |
1481 ms |
51224 KB |
Output is correct |
8 |
Correct |
1085 ms |
56260 KB |
Output is correct |
9 |
Correct |
1754 ms |
56748 KB |
Output is correct |
10 |
Correct |
3570 ms |
61640 KB |
Output is correct |
11 |
Correct |
3653 ms |
56488 KB |
Output is correct |
12 |
Runtime error |
179 ms |
126972 KB |
Execution killed with signal 11 |
13 |
Runtime error |
176 ms |
127208 KB |
Execution killed with signal 11 |
14 |
Runtime error |
190 ms |
127872 KB |
Execution killed with signal 11 |
15 |
Runtime error |
180 ms |
131072 KB |
Execution killed with signal 11 |
16 |
Runtime error |
171 ms |
131072 KB |
Execution killed with signal 11 |
17 |
Runtime error |
174 ms |
131072 KB |
Execution killed with signal 11 |