답안 #431787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431787 2021-06-17T15:28:41 Z Kerim Regions (IOI09_regions) C++17
100 / 100
4224 ms 92476 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=500;
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 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: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);
      |   ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 10 ms 9744 KB Output is correct
4 Correct 11 ms 9672 KB Output is correct
5 Correct 14 ms 9804 KB Output is correct
6 Correct 27 ms 9928 KB Output is correct
7 Correct 38 ms 9936 KB Output is correct
8 Correct 37 ms 10048 KB Output is correct
9 Correct 62 ms 10804 KB Output is correct
10 Correct 97 ms 10792 KB Output is correct
11 Correct 130 ms 11352 KB Output is correct
12 Correct 169 ms 12152 KB Output is correct
13 Correct 191 ms 11712 KB Output is correct
14 Correct 217 ms 12512 KB Output is correct
15 Correct 301 ms 17140 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1161 ms 18144 KB Output is correct
2 Correct 1375 ms 16260 KB Output is correct
3 Correct 2180 ms 23384 KB Output is correct
4 Correct 299 ms 13248 KB Output is correct
5 Correct 401 ms 16748 KB Output is correct
6 Correct 600 ms 15620 KB Output is correct
7 Correct 874 ms 15884 KB Output is correct
8 Correct 1338 ms 26896 KB Output is correct
9 Correct 2272 ms 29804 KB Output is correct
10 Correct 4170 ms 39824 KB Output is correct
11 Correct 4224 ms 32908 KB Output is correct
12 Correct 1437 ms 52876 KB Output is correct
13 Correct 2164 ms 56276 KB Output is correct
14 Correct 2356 ms 64388 KB Output is correct
15 Correct 3670 ms 80620 KB Output is correct
16 Correct 3478 ms 92476 KB Output is correct
17 Correct 3085 ms 83304 KB Output is correct