Submission #431774

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
431774	2021-06-17T15:14:33 Z	Kerim	Regions (IOI09_regions)	C++17	50 / 100	8000 ms	48136 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=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);
		}
		fflush(stdout);
	}
	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);
      |   ~~~~~^~~~~~~~~~~~~~

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	5 ms	4936 KB	Output is correct
4	Correct	7 ms	4936 KB	Output is correct
5	Correct	12 ms	4936 KB	Output is correct
6	Correct	22 ms	5064 KB	Output is correct
7	Correct	35 ms	5064 KB	Output is correct
8	Correct	40 ms	5064 KB	Output is correct
9	Correct	63 ms	5704 KB	Output is correct
10	Correct	98 ms	5576 KB	Output is correct
11	Correct	210 ms	5960 KB	Output is correct
12	Correct	179 ms	6600 KB	Output is correct
13	Correct	414 ms	6088 KB	Output is correct
14	Correct	1177 ms	6712 KB	Output is correct
15	Correct	978 ms	11208 KB	Output is correct

Subtask #2

35.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4870 ms	11460 KB	Output is correct
2	Correct	6831 ms	9664 KB	Output is correct
3	Execution timed out	8035 ms	14340 KB	Time limit exceeded
4	Correct	333 ms	6860 KB	Output is correct
5	Correct	487 ms	9660 KB	Output is correct
6	Correct	638 ms	27504 KB	Output is correct
7	Correct	1182 ms	37804 KB	Output is correct
8	Correct	1269 ms	48136 KB	Output is correct
9	Runtime error	50 ms	18084 KB	Execution killed with signal 11
10	Runtime error	51 ms	18932 KB	Execution killed with signal 11
11	Runtime error	51 ms	16372 KB	Execution killed with signal 11
12	Runtime error	62 ms	18444 KB	Execution killed with signal 11
13	Runtime error	55 ms	17960 KB	Execution killed with signal 11
14	Runtime error	67 ms	17708 KB	Execution killed with signal 11
15	Runtime error	53 ms	18988 KB	Execution killed with signal 11
16	Runtime error	52 ms	19024 KB	Execution killed with signal 11
17	Runtime error	54 ms	18800 KB	Execution killed with signal 11