답안 #431784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431784 2021-06-17T15:24:03 Z Kerim Regions (IOI09_regions) C++17
100 / 100
5729 ms 118432 KB
#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

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);
      |   ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 8 ms 9748 KB Output is correct
5 Correct 13 ms 9800 KB Output is correct
6 Correct 26 ms 9928 KB Output is correct
7 Correct 37 ms 9984 KB Output is correct
8 Correct 43 ms 10044 KB Output is correct
9 Correct 63 ms 10804 KB Output is correct
10 Correct 98 ms 10732 KB Output is correct
11 Correct 111 ms 11296 KB Output is correct
12 Correct 178 ms 12152 KB Output is correct
13 Correct 201 ms 11908 KB Output is correct
14 Correct 236 ms 12496 KB Output is correct
15 Correct 235 ms 17144 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1170 ms 18248 KB Output is correct
2 Correct 1337 ms 16692 KB Output is correct
3 Correct 2145 ms 23572 KB Output is correct
4 Correct 314 ms 13356 KB Output is correct
5 Correct 402 ms 16656 KB Output is correct
6 Correct 708 ms 34624 KB Output is correct
7 Correct 893 ms 44256 KB Output is correct
8 Correct 1214 ms 57432 KB Output is correct
9 Correct 2703 ms 70368 KB Output is correct
10 Correct 2873 ms 113732 KB Output is correct
11 Correct 5729 ms 104024 KB Output is correct
12 Correct 1352 ms 67044 KB Output is correct
13 Correct 2005 ms 70160 KB Output is correct
14 Correct 2659 ms 81504 KB Output is correct
15 Correct 3498 ms 106700 KB Output is correct
16 Correct 3492 ms 118432 KB Output is correct
17 Correct 3037 ms 100664 KB Output is correct