oj.uz

Submission #730348

# Submission time Handle Problem Language Result Execution time Memory
730348 2023-04-25T17:47:57 Z NintsiChkhaidze Regions (IOI09_regions) C++17
70 / 100
 6425 ms 131072 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
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 5624 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 11 ms 5712 KB Output is correct
6 Correct 19 ms 5840 KB Output is correct
7 Correct 25 ms 5712 KB Output is correct
8 Correct 33 ms 5840 KB Output is correct
9 Correct 39 ms 6864 KB Output is correct
10 Correct 69 ms 6352 KB Output is correct
11 Correct 137 ms 6864 KB Output is correct
12 Correct 167 ms 7888 KB Output is correct
13 Correct 229 ms 7504 KB Output is correct
14 Correct 377 ms 8016 KB Output is correct
15 Correct 415 ms 15568 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1358 ms 19464 KB Output is correct
2 Correct 1391 ms 13824 KB Output is correct
3 Correct 2920 ms 29108 KB Output is correct
4 Correct 394 ms 8340 KB Output is correct
5 Correct 429 ms 12752 KB Output is correct
6 Correct 1778 ms 10620 KB Output is correct
7 Correct 2389 ms 11980 KB Output is correct
8 Correct 2187 ms 24772 KB Output is correct
9 Correct 3880 ms 20600 KB Output is correct
10 Correct 6425 ms 33972 KB Output is correct
11 Correct 6089 ms 22404 KB Output is correct
12 Incorrect 2025 ms 76732 KB Output isn't correct
13 Incorrect 2851 ms 81132 KB Output isn't correct
14 Incorrect 2923 ms 91384 KB Output isn't correct
15 Runtime error 154 ms 131072 KB Execution killed with signal 9
16 Runtime error 142 ms 131072 KB Execution killed with signal 9
17 Runtime error 141 ms 131072 KB Execution killed with signal 9