oj.uz

Submission #799627

# Submission time Handle Problem Language Result Execution time Memory
799627 2023-07-31T16:49:56 Z I_Love_EliskaM_ Regions (IOI09_regions) C++14
100 / 100
 6857 ms 105168 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=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: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 5 ms 10320 KB Output is correct
2 Correct 5 ms 10320 KB Output is correct
3 Correct 6 ms 10320 KB Output is correct
4 Correct 9 ms 10320 KB Output is correct
5 Correct 9 ms 10448 KB Output is correct
6 Correct 21 ms 10704 KB Output is correct
7 Correct 23 ms 10832 KB Output is correct
8 Correct 37 ms 10960 KB Output is correct
9 Correct 57 ms 12368 KB Output is correct
10 Correct 96 ms 13952 KB Output is correct
11 Correct 133 ms 15440 KB Output is correct
12 Correct 173 ms 17880 KB Output is correct
13 Correct 216 ms 18384 KB Output is correct
14 Correct 343 ms 19912 KB Output is correct
15 Correct 456 ms 26192 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2439 ms 31988 KB Output is correct
2 Correct 2543 ms 31868 KB Output is correct
3 Correct 4802 ms 39040 KB Output is correct
4 Correct 352 ms 22444 KB Output is correct
5 Correct 373 ms 26952 KB Output is correct
6 Correct 498 ms 32720 KB Output is correct
7 Correct 1427 ms 42952 KB Output is correct
8 Correct 1346 ms 58616 KB Output is correct
9 Correct 3434 ms 76672 KB Output is correct
10 Correct 4610 ms 96396 KB Output is correct
11 Correct 6857 ms 93564 KB Output is correct
12 Correct 1954 ms 86528 KB Output is correct
13 Correct 2836 ms 86988 KB Output is correct
14 Correct 3058 ms 90616 KB Output is correct
15 Correct 5128 ms 97768 KB Output is correct
16 Correct 5461 ms 105168 KB Output is correct
17 Correct 4722 ms 102588 KB Output is correct