oj.uz

답안 #730364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
730364 2023-04-25T18:04:21 Z NintsiChkhaidze Regions (IOI09_regions) C++17
100 / 100
 5927 ms 91848 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ll long long
using namespace std;
 
const int N = 2e5+5,Bl=705,C = 200000/(Bl - 5) + 5;
 
vector <int> v[N],st[25005],ynull;
int r[N],tin[N],tout[N],id[25005];
int fen[N],B,r1,r2,timer;
int k[C][25005],DP[C][25005],ans;
bool big[25005];
 
int get(int idx){
	int s=0;
	while(idx){
		s+=fen[idx];
		idx -= (idx&(-idx));
	}
	return s;
}
void upd(int idx,int val){
	while (idx <= 200000){
		fen[idx] += val;
		idx += (idx & (-idx));
	}
}
vector <int> dfs(int x,int par, vector <int> P){
	tin[x] = ++timer;
	vector <int> vec = ynull,Pnew = ynull;
 
	if (x != 1){
		for (int i=0;i<B;i++) Pnew[i] += P[i];
		if (big[r[par]]) Pnew[id[r[par]] - 1]++;
	}
	vector <int> o;
	for (int to: v[x])
		if (to != par) {
			o = dfs(to,x,Pnew);
			for (int i = 0; i < B; i++) vec[i] += o[i];
			if (big[r[to]]) vec[id[r[to]] - 1]++;
		}
 
	for (int i=0;i<B;i++){
		k[i+1][r[x]] += vec[i];
		DP[i+1][r[x]] += Pnew[i];
	}
 
	tout[x] = timer;
	return vec;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,R,q;
	cin>>n>>R>>q;
 
	cin>>r[1]; st[r[1]].pb(1);
	for(int i=2;i<=n;i++){
		cin>>r1>>r[i];
		st[r[i]].pb(i);
		v[r1].pb(i);
		v[i].pb(r1);
	}
	
	B = 0;
	for (int i = 1; i <= R; i++){
		if ((int)st[i].size() > Bl){
			++B;
			id[i] = B; 
			big[i] = 1; 
		}
	}
	
	for (int i=0;i<B;i++) ynull.pb(0);
	dfs(1,1,ynull);
	while (q--){
		cin>>r1>>r2;
		if (!big[r1] && !big[r2]){
			ans=0;
			for (int x: st[r2]) upd(tin[x],1);
			for (int x: st[r1]) ans += get(tout[x]) - get(tin[x] - 1);
			for (int x: st[r2]) upd(tin[x],-1);
			cout<<ans<<endl;
		}else if (big[r2]){
			cout<<k[id[r2]][r1]<<endl;
		}else{
			cout<<DP[id[r1]][r2]<<endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 10 ms 5712 KB Output is correct
6 Correct 17 ms 5840 KB Output is correct
7 Correct 30 ms 5712 KB Output is correct
8 Correct 44 ms 5712 KB Output is correct
9 Correct 41 ms 6864 KB Output is correct
10 Correct 80 ms 6224 KB Output is correct
11 Correct 152 ms 6480 KB Output is correct
12 Correct 153 ms 7584 KB Output is correct
13 Correct 201 ms 6964 KB Output is correct
14 Correct 369 ms 7248 KB Output is correct
15 Correct 418 ms 15824 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1763 ms 14004 KB Output is correct
2 Correct 1337 ms 10712 KB Output is correct
3 Correct 2914 ms 22452 KB Output is correct
4 Correct 367 ms 7632 KB Output is correct
5 Correct 449 ms 12704 KB Output is correct
6 Correct 1474 ms 9544 KB Output is correct
7 Correct 2140 ms 10440 KB Output is correct
8 Correct 2554 ms 24904 KB Output is correct
9 Correct 4082 ms 17596 KB Output is correct
10 Correct 5927 ms 33004 KB Output is correct
11 Correct 5896 ms 17360 KB Output is correct
12 Correct 1709 ms 17040 KB Output is correct
13 Correct 2281 ms 21828 KB Output is correct
14 Correct 2836 ms 22688 KB Output is correct
15 Correct 5047 ms 37592 KB Output is correct
16 Correct 5128 ms 73284 KB Output is correct
17 Correct 4517 ms 91848 KB Output is correct