Submission #431784

#	Time	Username	Problem	Language	Result	Execution time	Memory
431784		Kerim	Regions (IOI09_regions)	C++17	100 / 100	5729 ms	118432 KiB

regions

#include "bits/stdc++.h"
#define MAXN 200009
#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];
vector<PII>comp[MAXN];
int who[MAXN],mx[MAXN],who_color[MAXN];
int cnt[MAXN],sub[MAXN];
int bs[N/K+3][C];
int sb[C][N/K+3];
int heavy[MAXN];
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;
}
map<PII,int>cache;
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();
	int res;
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		if(cache.find(mp(a,b))==cache.end()){
			if(~id[a])res = bs[id[a]][b];
			else if(~id[b])res = sb[a][id[b]];
			else{
				//ss
				res=0;
				for(int i=0;i<int(comp[a].size());i++)
					res+=get(b,comp[a][i]);
			}
			cache[mp(a,b)]=res;
		}
		printf("%d\n",cache[mp(a,b)]);
		fflush(stdout);
	}
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85