oj.uz

Submission #754367

# Submission time Handle Problem Language Result Execution time Memory
754367 2023-06-07T15:02:06 Z TimDee Regions (IOI09_regions) C++17
85 / 100
 8000 ms 99584 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=325;
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 10356 KB Output is correct
2 Correct 6 ms 10320 KB Output is correct
3 Correct 6 ms 10304 KB Output is correct
4 Correct 18 ms 10368 KB Output is correct
5 Correct 17 ms 10400 KB Output is correct
6 Correct 28 ms 10624 KB Output is correct
7 Correct 31 ms 10832 KB Output is correct
8 Correct 49 ms 10960 KB Output is correct
9 Correct 64 ms 12240 KB Output is correct
10 Correct 171 ms 13856 KB Output is correct
11 Correct 235 ms 15400 KB Output is correct
12 Correct 246 ms 17756 KB Output is correct
13 Correct 359 ms 18384 KB Output is correct
14 Correct 588 ms 20048 KB Output is correct
15 Correct 775 ms 24972 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4336 ms 31616 KB Output is correct
2 Correct 4987 ms 31808 KB Output is correct
3 Correct 7866 ms 37932 KB Output is correct
4 Correct 522 ms 22416 KB Output is correct
5 Correct 728 ms 26316 KB Output is correct
6 Correct 698 ms 32496 KB Output is correct
7 Correct 2374 ms 43340 KB Output is correct
8 Correct 1996 ms 56580 KB Output is correct
9 Correct 4991 ms 76132 KB Output is correct
10 Correct 6817 ms 93796 KB Output is correct
11 Execution timed out 8074 ms 93424 KB Time limit exceeded
12 Correct 3321 ms 86428 KB Output is correct
13 Correct 4615 ms 86352 KB Output is correct
14 Correct 4644 ms 90316 KB Output is correct
15 Execution timed out 8032 ms 95632 KB Time limit exceeded
16 Execution timed out 8050 ms 99584 KB Time limit exceeded
17 Correct 7167 ms 97716 KB Output is correct