Submission #1132055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132055		ByeWorld	Regions (IOI09_regions)	C++20	100 / 100	3721 ms	130068 KiB

regions

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int SQRT = 510;
const int MAXA = 55;
const int MOD = 1e9+7;
const int INF = 1e9+10;
const int LOG = 21;
const ld EPS = 1e-12;

int n, r, k, a[MAXN], siz;
vector <int> adj[MAXN], idx[MAXN], big;
int in[MAXN],out[MAXN],tim, par[MAXN], bigidx[MAXN];
int heavy[MAXA+5][MAXA+5], up[MAXN][MAXA+5], dw[MAXN][MAXA+5];

void dfs(int nw){
	in[nw] = ++tim;
	for(int i=0; i<siz; i++) up[nw][i] = up[par[nw]][i];
	if(bigidx[a[nw] ] != -1)
		up[nw][bigidx[ a[nw] ]]++, dw[nw][bigidx[ a[nw] ]]++;

	for(auto nx : adj[nw]){
		dfs(nx);
		for(int i=0; i<siz; i++)
			dw[nw][i] += dw[nx][i];
	}
	out[nw] = tim;
}
struct seg {
	int st[MAXN+10];
	int que(int x){
		int te = 0;
		for(; x>=1; x-=(x&(-x))) te += st[x];
		return te;
	}
	void upd(int x,int y){
		for(;x<=MAXN;x+=(x&(-x)))
			st[x] += y;
	}
} A;
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>r>>k;
	cin >> a[1]; idx[a[1]].pb(1);
	for(int i=2; i<=n; i++){
		cin>>par[i]>>a[i]; adj[par[i]].pb(i);
		idx[a[i]].pb(i);
	}
	for(int i=1; i<=r; i++){
		if(idx[i].size() >= SQRT) bigidx[i]=big.size(), big.pb(i);
		else bigidx[i] = -1;
	}
	siz = big.size();
	dfs(1);
	for(int i=0; i<siz; i++){
		for(int j=0; j<siz; j++){
			// cout << big[i] << ' ' << big[j] << " p\n";
			for(auto id : idx[big[j]]){
				// cout << id << " pp\n";
				heavy[i][j] += up[id][i];
			}
		}
	}

	while(k--){
		int x, y; cin>>x>>y; // x di atas y, xy colornya
		int ans = 0;
		if(idx[x].size()<SQRT){
			if(idx[y].size()<SQRT){
				for(auto id : idx[y]) A.upd(in[id], 1);
				for(auto id : idx[x]) 
					ans += A.que(out[id])-A.que(in[id]-1);
				for(auto id : idx[y]) A.upd(in[id], -1);

			} else {
				for(auto id : idx[x])
					ans += dw[id][bigidx[ y ]];
			} 
		} else {
			if(idx[y].size()<SQRT){ 
				for(auto id : idx[y])
					ans += up[id][bigidx[ x ]];
			} else { // big-big
				// cout << "bigbig\n";
				ans = heavy[ bigidx[x] ][ bigidx[y] ];
			} 
		}
		cout << ans << endl;
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85