| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 431771 |
2021-06-17T15:13:22 Z |
Kerim |
Regions (IOI09_regions) |
C++17 |
|
275 ms |
48124 KB |
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int C=25009;
const int K=300;
const int N=2e5+5;
int id[MAXN],idx,a[MAXN];
vector<int>adj[MAXN],comp[MAXN];
int who[MAXN],mx[MAXN],who_color[MAXN];
int cnt[MAXN],sub[MAXN];
int bs[N/K+3][C];
int heavy[MAXN];
int sb[C][N/K+3];
int tin[MAXN],tout[MAXN],T;
void pre(int nd=1){
tin[nd]=++T;
sub[nd]=1;
for(auto to:adj[nd]){
pre(to);
sub[nd]+=sub[to];
if(umax(mx[nd],sub[to]))
who[nd]=to;
}
tout[nd]=T;
}
//bb, bs
void dfs0(int color_id,int nd=1,int cnt_black=0){
bs[color_id][a[nd]]+=cnt_black;
cnt_black+=(~id[a[nd]] and id[a[nd]]==color_id);
for(auto to:adj[nd])
dfs0(color_id,to,cnt_black);
}
//sb
void add(int nd){
cnt[a[nd]]++;
for(auto to:adj[nd])
add(to);
}
void rem(int nd){
cnt[a[nd]]--;
for(auto to:adj[nd])
rem(to);
}
void dfs1(int nd=1,int keep=1){
for(auto to:adj[nd])
if(to!=who[nd])
dfs1(to,0);
if(who[nd])
dfs1(who[nd],1);
for(auto to:adj[nd])
if(to!=who[nd])
add(to);
cnt[a[nd]]++;
//here you have all color's cnt of my subtree
for(int c=0;c<idx;c++)
sb[a[nd]][c]+=cnt[who_color[c]];
if(!keep)
rem(nd);
}
int ata(int x,int y){
return (tin[x]<=tin[y] and tout[y]<=tout[x]);
}
bool is_heavy(int x){
return (int(comp[x].size())>K);
}
int main(){
//~ freopen("file.in", "r", stdin);
int n,c,q;
scanf("%d%d%d",&n,&c,&q);
scanf("%d",&a[1]);
comp[a[1]].pb(1);
for(int i=2;i<=n;i++){
int p;
scanf("%d%d",&p,&a[i]);
adj[p].pb(i);
comp[a[i]].pb(i);
}
idx=0;
for(int i=1;i<=c;i++){
if(is_heavy(i)){
who_color[idx]=i;
id[i]=idx++;
}
else
id[i]=-1;
}
for(int i=0;i<idx;i++)
dfs0(i);
pre();
dfs1();
while(q--){
int a,b;
scanf("%d%d",&a,&b);
assert(a!=b);
if(~id[a])
printf("%d\n",bs[id[a]][b]);
else if(~id[b])
printf("%d\n",sb[a][id[b]]);
else{
//ss
//|S_a|*|S_b|
int res=0;
for(int i=0;i<int(comp[a].size());i++)
for(int j=0;j<int(comp[b].size());j++)
res+=(ata(comp[a][i],comp[b][j]));
printf("%d\n",res);
}
}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d%d%d",&n,&c,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d",&a[1]);
| ~~~~~^~~~~~~~~~~~
regions.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d%d",&p,&a[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3 ms |
4936 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
3 ms |
4936 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
3 ms |
4936 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
3 ms |
4936 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
4 ms |
5120 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
3 ms |
5064 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
4 ms |
5120 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
4 ms |
5064 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
6 ms |
5704 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
8 ms |
5596 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
12 ms |
5876 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
12 ms |
6600 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
20 ms |
6060 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
19 ms |
6728 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
22 ms |
11208 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
86 ms |
11344 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
75 ms |
9652 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
54 ms |
14272 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
20 ms |
6856 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
18 ms |
9672 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
141 ms |
27544 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
179 ms |
37696 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
275 ms |
48124 KB |
Time limit exceeded (wall clock) |
| 9 |
Runtime error |
51 ms |
18152 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
50 ms |
18896 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
52 ms |
16388 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
53 ms |
18452 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
59 ms |
17980 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
69 ms |
17664 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
54 ms |
18984 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
51 ms |
19008 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
57 ms |
18780 KB |
Execution killed with signal 11 |
