oj.uz

Submission #754347

# Submission time Handle Problem Language Result Execution time Memory
754347 2023-06-07T14:15:29 Z TimDee Regions (IOI09_regions) C++17
95 / 100
 8000 ms 105248 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=350;
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 6 ms 10320 KB Output is correct
3 Correct 6 ms 10320 KB Output is correct
4 Correct 10 ms 10320 KB Output is correct
5 Correct 12 ms 10448 KB Output is correct
6 Correct 20 ms 10576 KB Output is correct
7 Correct 28 ms 10820 KB Output is correct
8 Correct 33 ms 10960 KB Output is correct
9 Correct 59 ms 12368 KB Output is correct
10 Correct 100 ms 13904 KB Output is correct
11 Correct 168 ms 15440 KB Output is correct
12 Correct 198 ms 17864 KB Output is correct
13 Correct 284 ms 18384 KB Output is correct
14 Correct 452 ms 19960 KB Output is correct
15 Correct 629 ms 26128 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3082 ms 32012 KB Output is correct
2 Correct 3435 ms 31864 KB Output is correct
3 Correct 6077 ms 39060 KB Output is correct
4 Correct 386 ms 22452 KB Output is correct
5 Correct 476 ms 26952 KB Output is correct
6 Correct 642 ms 32720 KB Output is correct
7 Correct 1728 ms 43164 KB Output is correct
8 Correct 1592 ms 58568 KB Output is correct
9 Correct 4048 ms 76672 KB Output is correct
10 Correct 5416 ms 96372 KB Output is correct
11 Execution timed out 8036 ms 93432 KB Time limit exceeded
12 Correct 2618 ms 86524 KB Output is correct
13 Correct 3619 ms 86948 KB Output is correct
14 Correct 3731 ms 90544 KB Output is correct
15 Correct 6738 ms 97864 KB Output is correct
16 Correct 7067 ms 105248 KB Output is correct
17 Correct 5651 ms 102584 KB Output is correct