oj.uz

Submission #730323

# Submission time Handle Problem Language Result Execution time Memory
730323 2023-04-25T17:20:00 Z NintsiChkhaidze Regions (IOI09_regions) C++17
55 / 100
 5819 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];
int r[N],tin[N],tout[N],cnt[N],timer,id[N],rev[N],dp[N][505];
int fen[N],B,k[25005][505],DP[505][N];
bool big[N],small[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; 
		}else{
			small[i] = 1;
		}
	}

	dfs(1,1);
	while (q--){
		int r1,r2,ans=0;
		cin>>r1>>r2;

		if (small[r1] && small[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 4 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 11 ms 5584 KB Output is correct
6 Correct 18 ms 5712 KB Output is correct
7 Correct 30 ms 5712 KB Output is correct
8 Correct 32 ms 5712 KB Output is correct
9 Correct 61 ms 6352 KB Output is correct
10 Correct 82 ms 6224 KB Output is correct
11 Correct 106 ms 6480 KB Output is correct
12 Correct 148 ms 7120 KB Output is correct
13 Correct 242 ms 6864 KB Output is correct
14 Correct 337 ms 7248 KB Output is correct
15 Correct 412 ms 11524 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 131072 KB Execution killed with signal 9
2 Runtime error 91 ms 131072 KB Execution killed with signal 9
3 Runtime error 76 ms 131072 KB Execution killed with signal 9
4 Correct 288 ms 7504 KB Output is correct
5 Correct 331 ms 9960 KB Output is correct
6 Correct 1636 ms 8964 KB Output is correct
7 Correct 2164 ms 9912 KB Output is correct
8 Correct 2233 ms 17480 KB Output is correct
9 Correct 3691 ms 15748 KB Output is correct
10 Correct 5819 ms 23496 KB Output is correct
11 Correct 5738 ms 17224 KB Output is correct
12 Runtime error 116 ms 131072 KB Execution killed with signal 9
13 Runtime error 108 ms 131072 KB Execution killed with signal 9
14 Runtime error 136 ms 131072 KB Execution killed with signal 9
15 Runtime error 129 ms 131072 KB Execution killed with signal 9
16 Runtime error 111 ms 131072 KB Execution killed with signal 9
17 Runtime error 113 ms 131072 KB Execution killed with signal 9