oj.uz

Submission #754361

# Submission time Handle Problem Language Result Execution time Memory
754361 2023-06-07T14:57:51 Z TimDee Regions (IOI09_regions) C++17
85 / 100
 8000 ms 131072 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=250;
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 10380 KB Output is correct
2 Correct 6 ms 10368 KB Output is correct
3 Correct 9 ms 10308 KB Output is correct
4 Correct 11 ms 10408 KB Output is correct
5 Correct 14 ms 10488 KB Output is correct
6 Correct 24 ms 10704 KB Output is correct
7 Correct 44 ms 10732 KB Output is correct
8 Correct 24 ms 10992 KB Output is correct
9 Correct 73 ms 12352 KB Output is correct
10 Correct 111 ms 13904 KB Output is correct
11 Correct 203 ms 15336 KB Output is correct
12 Correct 178 ms 17784 KB Output is correct
13 Correct 362 ms 18380 KB Output is correct
14 Correct 700 ms 20072 KB Output is correct
15 Correct 797 ms 26176 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4272 ms 32032 KB Output is correct
2 Correct 2932 ms 32220 KB Output is correct
3 Correct 7649 ms 38980 KB Output is correct
4 Correct 364 ms 22404 KB Output is correct
5 Correct 558 ms 26976 KB Output is correct
6 Correct 765 ms 32700 KB Output is correct
7 Correct 1970 ms 43848 KB Output is correct
8 Correct 1686 ms 58600 KB Output is correct
9 Correct 4784 ms 82960 KB Output is correct
10 Correct 7440 ms 96468 KB Output is correct
11 Runtime error 4145 ms 131072 KB Execution killed with signal 9
12 Correct 3130 ms 86432 KB Output is correct
13 Correct 4435 ms 86860 KB Output is correct
14 Correct 4877 ms 90544 KB Output is correct
15 Execution timed out 8084 ms 97668 KB Time limit exceeded
16 Execution timed out 8010 ms 105208 KB Time limit exceeded
17 Correct 7532 ms 102592 KB Output is correct