Submission #431777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
431777	2021-06-17T15:19:38 Z	Kerim	Regions (IOI09_regions)	C++17	55 / 100	2441 ms	53740 KB

regions

#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=250;
const int N=2e5+5;
int id[MAXN],idx,a[MAXN];
vector<int>adj[MAXN];
vector<PII>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);
}
//log(S_i<K)~=8
int get(int x,PII tmp){
	int a=lower_bound(all(comp[x]),mp(tmp.ff,-1))-comp[x].begin();
	int b=upper_bound(all(comp[x]),mp(tmp.ss,INF))-comp[x].begin();
	return b-a;
}
int main(){
    //~ freopen("file.in", "r", stdin);
    int n,c,q;
    scanf("%d%d%d",&n,&c,&q);
    scanf("%d",&a[1]);
    for(int i=2;i<=n;i++){
		int p;
		scanf("%d%d",&p,&a[i]);
		adj[p].pb(i);
	}
	pre();
	for(int i=1;i<=n;i++)
		comp[a[i]].pb(mp(tin[i],tout[i]));
	idx=0;
	for(int i=1;i<=c;i++){
		sort(all(comp[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);
	dfs1();
	ll res;
	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
			res=0;
			for(int i=0;i<int(comp[a].size());i++)
				res+=get(b,comp[a][i]);
			printf("%lld\n",res);
		}
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d%d%d",&n,&c,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d",&a[1]);
      |     ~~~~~^~~~~~~~~~~~
regions.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d%d",&p,&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4936 KB	Output is correct
2	Correct	4 ms	4936 KB	Output is correct
3	Correct	4 ms	4968 KB	Output is correct
4	Correct	5 ms	4936 KB	Output is correct
5	Correct	12 ms	4936 KB	Output is correct
6	Correct	13 ms	5064 KB	Output is correct
7	Correct	31 ms	5064 KB	Output is correct
8	Correct	43 ms	5064 KB	Output is correct
9	Correct	34 ms	5832 KB	Output is correct
10	Correct	81 ms	5576 KB	Output is correct
11	Correct	129 ms	5964 KB	Output is correct
12	Correct	141 ms	6728 KB	Output is correct
13	Correct	208 ms	6344 KB	Output is correct
14	Correct	283 ms	6992 KB	Output is correct
15	Correct	319 ms	11464 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1279 ms	12016 KB	Output is correct
2	Correct	1216 ms	10688 KB	Output is correct
3	Correct	2441 ms	15076 KB	Output is correct
4	Correct	255 ms	7112 KB	Output is correct
5	Correct	254 ms	9800 KB	Output is correct
6	Correct	653 ms	30696 KB	Output is correct
7	Correct	1049 ms	43428 KB	Output is correct
8	Correct	1091 ms	53740 KB	Output is correct
9	Runtime error	44 ms	16508 KB	Execution killed with signal 11
10	Runtime error	45 ms	17004 KB	Execution killed with signal 11
11	Runtime error	60 ms	14436 KB	Execution killed with signal 11
12	Runtime error	55 ms	16960 KB	Execution killed with signal 11
13	Runtime error	53 ms	16332 KB	Execution killed with signal 11
14	Runtime error	56 ms	15956 KB	Execution killed with signal 11
15	Runtime error	49 ms	16996 KB	Execution killed with signal 11
16	Runtime error	50 ms	16976 KB	Execution killed with signal 11
17	Runtime error	55 ms	16960 KB	Execution killed with signal 11