oj.uz

Submission #754366

# Submission time Handle Problem Language Result Execution time Memory
754366 2023-06-07T15:01:48 Z TimDee Regions (IOI09_regions) C++17
85 / 100
 8000 ms 99624 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=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: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 5 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 8 ms 10320 KB Output is correct
5 Correct 14 ms 10448 KB Output is correct
6 Correct 37 ms 10576 KB Output is correct
7 Correct 33 ms 10832 KB Output is correct
8 Correct 42 ms 10960 KB Output is correct
9 Correct 76 ms 12276 KB Output is correct
10 Correct 110 ms 13904 KB Output is correct
11 Correct 181 ms 15396 KB Output is correct
12 Correct 253 ms 17744 KB Output is correct
13 Correct 338 ms 18316 KB Output is correct
14 Correct 537 ms 19888 KB Output is correct
15 Correct 770 ms 24960 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4059 ms 31596 KB Output is correct
2 Correct 3844 ms 31812 KB Output is correct
3 Correct 7235 ms 38000 KB Output is correct
4 Correct 379 ms 22504 KB Output is correct
5 Correct 680 ms 26196 KB Output is correct
6 Correct 743 ms 32520 KB Output is correct
7 Correct 2448 ms 43048 KB Output is correct
8 Correct 1933 ms 56652 KB Output is correct
9 Correct 5373 ms 76120 KB Output is correct
10 Correct 7559 ms 93832 KB Output is correct
11 Execution timed out 8032 ms 93456 KB Time limit exceeded
12 Correct 3337 ms 86396 KB Output is correct
13 Correct 4900 ms 86296 KB Output is correct
14 Correct 4820 ms 90424 KB Output is correct
15 Execution timed out 8064 ms 95772 KB Time limit exceeded
16 Execution timed out 8037 ms 99624 KB Time limit exceeded
17 Correct 7632 ms 97704 KB Output is correct