oj.uz

Submission #754363

# Submission time Handle Problem Language Result Execution time Memory
754363 2023-06-07T14:58:02 Z TimDee Regions (IOI09_regions) C++17
85 / 100
 8000 ms 105220 KB 
#include <bits/stdc++.h>
using namespace std;

//#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=500;
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:13:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   13 | const int inf=1e18;
      |               ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10264 KB Output is correct
2 Correct 6 ms 10344 KB Output is correct
3 Correct 10 ms 10320 KB Output is correct
4 Correct 12 ms 10320 KB Output is correct
5 Correct 12 ms 10540 KB Output is correct
6 Correct 14 ms 10596 KB Output is correct
7 Correct 26 ms 10832 KB Output is correct
8 Correct 48 ms 10960 KB Output is correct
9 Correct 77 ms 12368 KB Output is correct
10 Correct 123 ms 13868 KB Output is correct
11 Correct 214 ms 15408 KB Output is correct
12 Correct 293 ms 17808 KB Output is correct
13 Correct 353 ms 18324 KB Output is correct
14 Correct 558 ms 19924 KB Output is correct
15 Correct 775 ms 26116 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4526 ms 32036 KB Output is correct
2 Correct 4627 ms 31868 KB Output is correct
3 Correct 7927 ms 39056 KB Output is correct
4 Correct 407 ms 22456 KB Output is correct
5 Correct 834 ms 26992 KB Output is correct
6 Correct 2683 ms 30728 KB Output is correct
7 Correct 3703 ms 41656 KB Output is correct
8 Correct 3332 ms 54288 KB Output is correct
9 Correct 5161 ms 76680 KB Output is correct
10 Execution timed out 8090 ms 86524 KB Time limit exceeded
11 Execution timed out 8060 ms 93524 KB Time limit exceeded
12 Correct 2565 ms 86536 KB Output is correct
13 Correct 4342 ms 86868 KB Output is correct
14 Correct 5137 ms 90560 KB Output is correct
15 Correct 7791 ms 97764 KB Output is correct
16 Execution timed out 8022 ms 105220 KB Time limit exceeded
17 Correct 6993 ms 102596 KB Output is correct