oj.uz

Submission #754368

# Submission time Handle Problem Language Result Execution time Memory
754368 2023-06-07T15:02:24 Z TimDee Regions (IOI09_regions) C++17
100 / 100
 7762 ms 99568 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

//#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];

const int inf=1e18;

const int K=375;
const int N=2e5+55;
const int M=25555;

int L[N],R[N];
int dp1[N/K][M];

const int sz=1<<18;
struct sgt {
	sgt *L, *R;
	int s;
	sgt() {
		L=R=NULL; s=0;
	}
	void add(int l, int r, int i) {
		s++;
		if (r-l==1) return;
		int m=(l+r)>>1;
		if (i<m) {
			if (!L) L=new sgt();
			L->add(l,m,i);
		} else {
			if (!R) R=new sgt();
			R->add(m,r,i);
		}
	}
	void add(int i) {
		add(0,sz,i);
	}
	int query(int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return 0;
		if (lx<=l && r<=rx) return s;
		int m=(l+r)>>1;
		int lq=L?L->query(l,m,lx,rx):0;
		int rq=R?R->query(m,r,lx,rx):0;
		return lq+rq;
	}
	int query(int l, int r) {
		return query(0,sz,l,r);
	}
};

vector<int> adj[N];
sgt st[N];
int reg[N];

int t=0;
void dfs(int u, int p) {
	L[u]=t++;
	R[u]=L[u];
	for(auto&v:adj[u]) {
		if (v==p) continue;
		dfs(v,u);
		R[u]=max(R[u],R[v]);
	}
}

vector<int> pos[M];
int comp[M];
int cnt[M];

void dfs(int u, int p, int c, int x) {
	c+=reg[u]==x;
	dp1[comp[x]][reg[u]]+=c;
	for(auto&v:adj[u]) {
		if (v==p) continue;
		dfs(v,u,c,x);
	}
}

void solve() {

	int n,r,q; cin>>n>>r>>q;
	forn(i,r) comp[i]=-1;
	cin>>reg[0]; --reg[0];
	forn(i,n-1) {
		int p,r; cin>>p>>r; --p, --r;
		adj[p].pb(i+1); reg[i+1]=r;
	}
	dfs(0,-1);
	forn(i,n) st[reg[i]].add(L[i]);
	forn(i,n) {
		cnt[reg[i]]++;
		pos[reg[i]].pb(i);
	}
	int z=0;
	forn(i,r) {
		if (cnt[i]<=K) continue;
		comp[i]=z++;
		dfs(0,-1,0,i);
	}

	forn(i,q) {
		int r1, r2; cin>>r1>>r2;
		--r1, --r2;
		if (cnt[r1]<=K) {
			int ans=0;
			for(auto&x:pos[r1]) {
				ans+=st[r2].query(L[x],R[x]+1);
			}
			cout<<ans<<'\n';
		} else {
			cout<<dp1[comp[r1]][r2]<<'\n';
		}
		cout.flush();
	}

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
}

Compilation message

regions.cpp:16:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int inf=1e18;
      |               ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10368 KB Output is correct
2 Correct 6 ms 10320 KB Output is correct
3 Correct 7 ms 10356 KB Output is correct
4 Correct 14 ms 10320 KB Output is correct
5 Correct 19 ms 10448 KB Output is correct
6 Correct 22 ms 10624 KB Output is correct
7 Correct 33 ms 10832 KB Output is correct
8 Correct 30 ms 10960 KB Output is correct
9 Correct 62 ms 12264 KB Output is correct
10 Correct 102 ms 13956 KB Output is correct
11 Correct 288 ms 15416 KB Output is correct
12 Correct 290 ms 17656 KB Output is correct
13 Correct 338 ms 18384 KB Output is correct
14 Correct 603 ms 19956 KB Output is correct
15 Correct 823 ms 24920 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4630 ms 31560 KB Output is correct
2 Correct 4577 ms 31800 KB Output is correct
3 Correct 7196 ms 37936 KB Output is correct
4 Correct 439 ms 22352 KB Output is correct
5 Correct 600 ms 26200 KB Output is correct
6 Correct 704 ms 32520 KB Output is correct
7 Correct 2622 ms 42844 KB Output is correct
8 Correct 1270 ms 56552 KB Output is correct
9 Correct 4359 ms 76124 KB Output is correct
10 Correct 5879 ms 93824 KB Output is correct
11 Correct 7762 ms 93476 KB Output is correct
12 Correct 2302 ms 86404 KB Output is correct
13 Correct 3649 ms 86340 KB Output is correct
14 Correct 4241 ms 90316 KB Output is correct
15 Correct 6445 ms 95720 KB Output is correct
16 Correct 6575 ms 99568 KB Output is correct
17 Correct 6038 ms 97708 KB Output is correct