oj.uz

Submission #754360

# Submission time Handle Problem Language Result Execution time Memory
754360 2023-06-07T14:57:23 Z TimDee Regions (IOI09_regions) C++17
80 / 100
 8000 ms 105172 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=300;
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 6 ms 10320 KB Output is correct
2 Correct 6 ms 10320 KB Output is correct
3 Correct 7 ms 10320 KB Output is correct
4 Correct 10 ms 10320 KB Output is correct
5 Correct 14 ms 10448 KB Output is correct
6 Correct 22 ms 10704 KB Output is correct
7 Correct 37 ms 10832 KB Output is correct
8 Correct 42 ms 10960 KB Output is correct
9 Correct 64 ms 12496 KB Output is correct
10 Correct 112 ms 13868 KB Output is correct
11 Correct 201 ms 15440 KB Output is correct
12 Correct 137 ms 17784 KB Output is correct
13 Correct 279 ms 18360 KB Output is correct
14 Correct 552 ms 20040 KB Output is correct
15 Correct 689 ms 26192 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2939 ms 32044 KB Output is correct
2 Correct 3199 ms 31868 KB Output is correct
3 Correct 5878 ms 39004 KB Output is correct
4 Correct 341 ms 22412 KB Output is correct
5 Correct 531 ms 26992 KB Output is correct
6 Correct 712 ms 32708 KB Output is correct
7 Correct 1834 ms 43728 KB Output is correct
8 Correct 2126 ms 58684 KB Output is correct
9 Correct 4551 ms 79692 KB Output is correct
10 Correct 7025 ms 96372 KB Output is correct
11 Execution timed out 8023 ms 103100 KB Time limit exceeded
12 Correct 3068 ms 86484 KB Output is correct
13 Correct 4542 ms 86908 KB Output is correct
14 Correct 4692 ms 90680 KB Output is correct
15 Execution timed out 8016 ms 97740 KB Time limit exceeded
16 Execution timed out 8050 ms 105172 KB Time limit exceeded
17 Execution timed out 8035 ms 102640 KB Time limit exceeded