oj.uz

Submission #730347

# Submission time Handle Problem Language Result Execution time Memory
730347 2023-04-25T17:45:04 Z NintsiChkhaidze Regions (IOI09_regions) C++17
70 / 100
 6394 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+1][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{
			cout<<DP[id[r1]][r2]<<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 4 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 9 ms 5584 KB Output is correct
6 Correct 23 ms 5840 KB Output is correct
7 Correct 17 ms 5712 KB Output is correct
8 Correct 33 ms 5712 KB Output is correct
9 Correct 60 ms 6724 KB Output is correct
10 Correct 100 ms 6224 KB Output is correct
11 Correct 143 ms 6508 KB Output is correct
12 Correct 183 ms 7468 KB Output is correct
13 Correct 236 ms 6864 KB Output is correct
14 Correct 342 ms 7240 KB Output is correct
15 Correct 471 ms 14656 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1520 ms 15360 KB Output is correct
2 Correct 1763 ms 11136 KB Output is correct
3 Correct 2865 ms 21816 KB Output is correct
4 Correct 384 ms 7588 KB Output is correct
5 Correct 449 ms 11984 KB Output is correct
6 Correct 1692 ms 9364 KB Output is correct
7 Correct 2567 ms 10312 KB Output is correct
8 Correct 2135 ms 22736 KB Output is correct
9 Correct 3496 ms 17200 KB Output is correct
10 Correct 5938 ms 30372 KB Output is correct
11 Correct 6394 ms 17428 KB Output is correct
12 Incorrect 1751 ms 47936 KB Output isn't correct
13 Incorrect 2473 ms 52136 KB Output isn't correct
14 Incorrect 2677 ms 59144 KB Output isn't correct
15 Incorrect 3933 ms 84640 KB Output isn't correct
16 Incorrect 4308 ms 116548 KB Output isn't correct
17 Runtime error 140 ms 131072 KB Execution killed with signal 9