oj.uz

답안 #730361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
730361 2023-04-25T18:02:19 Z NintsiChkhaidze Regions (IOI09_regions) C++17
90 / 100
 8000 ms 131072 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=405,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 4 ms 5584 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 4 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 16 ms 5712 KB Output is correct
6 Correct 23 ms 5860 KB Output is correct
7 Correct 41 ms 5712 KB Output is correct
8 Correct 45 ms 5712 KB Output is correct
9 Correct 97 ms 6864 KB Output is correct
10 Correct 106 ms 6272 KB Output is correct
11 Correct 210 ms 6536 KB Output is correct
12 Correct 176 ms 7624 KB Output is correct
13 Correct 306 ms 6844 KB Output is correct
14 Correct 405 ms 7324 KB Output is correct
15 Correct 564 ms 15908 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1815 ms 17048 KB Output is correct
2 Correct 1898 ms 10840 KB Output is correct
3 Correct 3766 ms 22456 KB Output is correct
4 Correct 511 ms 7560 KB Output is correct
5 Correct 593 ms 12744 KB Output is correct
6 Correct 568 ms 17324 KB Output is correct
7 Correct 1779 ms 14280 KB Output is correct
8 Correct 1465 ms 116156 KB Output is correct
9 Correct 4841 ms 17640 KB Output is correct
10 Runtime error 287 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8044 ms 17372 KB Time limit exceeded
12 Correct 2249 ms 17052 KB Output is correct
13 Correct 3223 ms 21744 KB Output is correct
14 Correct 3392 ms 23876 KB Output is correct
15 Correct 5740 ms 37604 KB Output is correct
16 Correct 6227 ms 73284 KB Output is correct
17 Correct 6076 ms 108196 KB Output is correct