oj.uz

답안 #431777

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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