oj.uz

Submission #730336

# Submission time Handle Problem Language Result Execution time Memory
730336 2023-04-25T17:40:12 Z NintsiChkhaidze Regions (IOI09_regions) C++17
55 / 100
 7109 ms 131072 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;

const int N = 2e5+5,Bl=505;

vector <int> v[N],st[25005],ynull;
int r[N],tin[N],tout[N],cnt[25005],timer,id[25005];
int fen[N],B,k[25005][Bl],DP[Bl][2505];
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]++;
		for (int i=0;i<B;i++)
			DP[i][r[x]] += Pnew[i];
	}

	for (int to: v[x])
		if (to != par) {
			vector <int> 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[r[x]][i + 1] += vec[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]; cnt[r[1]]++; st[r[1]].pb(1);
	for(int i=2;i<=n;i++){
		int p;
		cin>>p>>r[i];
		cnt[r[i]]++; st[r[i]].pb(i);
		v[p].pb(i);
		v[i].pb(p);
	}
	
	B = 0;
	for (int i = 1; i <= R; i++){
		if (cnt[i] > Bl){
			++B;
			id[i] = B; 
			big[i] = 1; 
		}
	}
	
	for (int i=0;i<B;i++) ynull.pb(0);
	dfs(1,1,ynull);
	while (q--){
		int r1,r2,ans=0;
		cin>>r1>>r2;

		if (!big[r1] && !big[r2]){
			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[r1][id[r2]]<<endl;
		}else{
			ans += DP[id[r1]][r2];
			cout<<ans<<endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory 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 7 ms 5584 KB Output is correct
5 Correct 10 ms 5584 KB Output is correct
6 Correct 23 ms 5840 KB Output is correct
7 Correct 35 ms 5712 KB Output is correct
8 Correct 35 ms 5712 KB Output is correct
9 Correct 47 ms 6736 KB Output is correct
10 Correct 94 ms 6224 KB Output is correct
11 Correct 180 ms 6480 KB Output is correct
12 Correct 181 ms 7376 KB Output is correct
13 Correct 238 ms 6944 KB Output is correct
14 Correct 329 ms 7248 KB Output is correct
15 Correct 449 ms 14672 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1544 ms 15356 KB Output isn't correct
2 Incorrect 1605 ms 11136 KB Output isn't correct
3 Incorrect 3275 ms 21808 KB Output isn't correct
4 Correct 410 ms 7628 KB Output is correct
5 Correct 491 ms 11996 KB Output is correct
6 Correct 1603 ms 9292 KB Output is correct
7 Correct 2190 ms 10268 KB Output is correct
8 Correct 2348 ms 22744 KB Output is correct
9 Correct 4011 ms 17084 KB Output is correct
10 Correct 6703 ms 30444 KB Output is correct
11 Correct 7109 ms 17436 KB Output is correct
12 Incorrect 1461 ms 47928 KB Output isn't correct
13 Incorrect 2132 ms 52140 KB Output isn't correct
14 Incorrect 2563 ms 59140 KB Output isn't correct
15 Incorrect 4705 ms 84636 KB Output isn't correct
16 Incorrect 4803 ms 116552 KB Output isn't correct
17 Runtime error 171 ms 131072 KB Execution killed with signal 9