oj.uz

Submission #730328

# Submission time Handle Problem Language Result Execution time Memory
730328 2023-04-25T17:27:06 Z NintsiChkhaidze Regions (IOI09_regions) C++17
45 / 100
 1248 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=165;

vector <int> v[N],st[25005];
int r[N],tin[N],tout[N],cnt[N],timer,id[N],dp[N][Bl];
int fen[N],B,k[25005][Bl],DP[Bl][N];
bool big[N];

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));
	}
}
void dfs(int x,int par){
	tin[x] = ++timer;

	if (x != 1){
		for (int i = 1; i <= B; i++)
			DP[i][x] += DP[i][par];
		if (big[r[par]])
			DP[id[r[par]]][x]++;
	}

	for (int to: v[x])
		if (to != par) {
			dfs(to,x);
			for (int i = 1; i <= B; i++)
				dp[x][i] += dp[to][i];
			if (big[r[to]]) dp[x][id[r[to]]]++;
		}

	for (int i = 1; i <= B; i++)
		k[r[x]][i] += dp[x][i];

	tout[x] = timer;
}
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; 
		}
	}

	dfs(1,1);
	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{
			for (int x: st[r2])
				ans += DP[id[r1]][x];
			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 6 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 12 ms 5584 KB Output is correct
6 Correct 30 ms 5712 KB Output is correct
7 Correct 40 ms 5712 KB Output is correct
8 Correct 36 ms 5712 KB Output is correct
9 Correct 67 ms 6352 KB Output is correct
10 Correct 104 ms 6140 KB Output is correct
11 Correct 154 ms 6404 KB Output is correct
12 Correct 195 ms 7120 KB Output is correct
13 Correct 243 ms 6864 KB Output is correct
14 Correct 391 ms 28764 KB Output is correct
15 Correct 300 ms 57988 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 861 ms 114604 KB Output isn't correct
2 Correct 1092 ms 109552 KB Output is correct
3 Runtime error 120 ms 131072 KB Execution killed with signal 9
4 Correct 426 ms 30728 KB Output is correct
5 Correct 533 ms 9936 KB Output is correct
6 Correct 591 ms 59300 KB Output is correct
7 Correct 1124 ms 81380 KB Output is correct
8 Correct 1248 ms 128132 KB Output is correct
9 Runtime error 165 ms 131072 KB Execution killed with signal 9
10 Runtime error 76 ms 30384 KB Execution killed with signal 11
11 Runtime error 94 ms 33344 KB Execution killed with signal 11
12 Runtime error 89 ms 31068 KB Execution killed with signal 11
13 Runtime error 79 ms 31132 KB Execution killed with signal 11
14 Runtime error 89 ms 32336 KB Execution killed with signal 11
15 Runtime error 91 ms 32720 KB Execution killed with signal 11
16 Runtime error 102 ms 32392 KB Execution killed with signal 11
17 Runtime error 87 ms 32384 KB Execution killed with signal 11