oj.uz

Submission #730321

# Submission time Handle Problem Language Result Execution time Memory
730321 2023-04-25T17:11:11 Z NintsiChkhaidze Regions (IOI09_regions) C++17
55 / 100
 6084 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];
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;
	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;

		// cout<<cnt[r1]<<" "<<cnt[r2]<<endl;
		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{
			assert(0);
			cout<<"?\n";
		}
	}
}

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 11 ms 5584 KB Output is correct
6 Correct 19 ms 5780 KB Output is correct
7 Correct 28 ms 5712 KB Output is correct
8 Correct 42 ms 5712 KB Output is correct
9 Correct 46 ms 6352 KB Output is correct
10 Correct 81 ms 6188 KB Output is correct
11 Correct 125 ms 6480 KB Output is correct
12 Correct 123 ms 7120 KB Output is correct
13 Correct 244 ms 6884 KB Output is correct
14 Correct 317 ms 7268 KB Output is correct
15 Correct 423 ms 11472 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 131072 KB Execution killed with signal 9
2 Runtime error 98 ms 131072 KB Execution killed with signal 9
3 Runtime error 70 ms 131072 KB Execution killed with signal 9
4 Correct 435 ms 7432 KB Output is correct
5 Correct 379 ms 9928 KB Output is correct
6 Correct 1552 ms 8980 KB Output is correct
7 Correct 2326 ms 10084 KB Output is correct
8 Correct 2373 ms 17424 KB Output is correct
9 Correct 3718 ms 15764 KB Output is correct
10 Correct 6084 ms 23432 KB Output is correct
11 Correct 5982 ms 17244 KB Output is correct
12 Runtime error 100 ms 131072 KB Execution killed with signal 9
13 Runtime error 105 ms 131072 KB Execution killed with signal 9
14 Runtime error 114 ms 131072 KB Execution killed with signal 9
15 Runtime error 131 ms 131072 KB Execution killed with signal 9
16 Runtime error 109 ms 131072 KB Execution killed with signal 9
17 Runtime error 110 ms 131072 KB Execution killed with signal 9