oj.uz

Submission #754343

# Submission time Handle Problem Language Result Execution time Memory
754343 2023-06-07T14:09:49 Z TimDee Regions (IOI09_regions) C++17
95 / 100
 8000 ms 105216 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=400;
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 8 ms 10320 KB Output is correct
4 Correct 7 ms 10384 KB Output is correct
5 Correct 12 ms 10448 KB Output is correct
6 Correct 23 ms 10704 KB Output is correct
7 Correct 39 ms 10728 KB Output is correct
8 Correct 42 ms 10960 KB Output is correct
9 Correct 75 ms 12424 KB Output is correct
10 Correct 89 ms 13900 KB Output is correct
11 Correct 188 ms 15440 KB Output is correct
12 Correct 217 ms 17864 KB Output is correct
13 Correct 284 ms 18336 KB Output is correct
14 Correct 471 ms 19988 KB Output is correct
15 Correct 756 ms 26056 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3701 ms 32072 KB Output is correct
2 Correct 4008 ms 31864 KB Output is correct
3 Correct 6657 ms 39020 KB Output is correct
4 Correct 321 ms 22432 KB Output is correct
5 Correct 508 ms 27092 KB Output is correct
6 Correct 561 ms 32624 KB Output is correct
7 Correct 2112 ms 42876 KB Output is correct
8 Correct 1661 ms 58568 KB Output is correct
9 Correct 4861 ms 76676 KB Output is correct
10 Correct 6040 ms 96424 KB Output is correct
11 Execution timed out 8051 ms 93616 KB Time limit exceeded
12 Correct 2856 ms 86468 KB Output is correct
13 Correct 3759 ms 86952 KB Output is correct
14 Correct 4354 ms 90548 KB Output is correct
15 Correct 6924 ms 97780 KB Output is correct
16 Correct 7150 ms 105216 KB Output is correct
17 Correct 6106 ms 102592 KB Output is correct