oj.uz

Submission #754365

# Submission time Handle Problem Language Result Execution time Memory
754365 2023-06-07T15:01:31 Z TimDee Regions (IOI09_regions) C++17
85 / 100
 8000 ms 99520 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=400;
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 5 ms 10320 KB Output is correct
3 Correct 7 ms 10320 KB Output is correct
4 Correct 10 ms 10364 KB Output is correct
5 Correct 11 ms 10448 KB Output is correct
6 Correct 24 ms 10576 KB Output is correct
7 Correct 29 ms 10832 KB Output is correct
8 Correct 46 ms 10960 KB Output is correct
9 Correct 60 ms 12240 KB Output is correct
10 Correct 125 ms 13956 KB Output is correct
11 Correct 204 ms 15312 KB Output is correct
12 Correct 233 ms 17744 KB Output is correct
13 Correct 325 ms 18324 KB Output is correct
14 Correct 531 ms 19996 KB Output is correct
15 Correct 594 ms 24908 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3636 ms 31680 KB Output is correct
2 Correct 4022 ms 31892 KB Output is correct
3 Correct 6607 ms 38080 KB Output is correct
4 Correct 416 ms 22404 KB Output is correct
5 Correct 633 ms 26252 KB Output is correct
6 Correct 650 ms 32572 KB Output is correct
7 Correct 2461 ms 42728 KB Output is correct
8 Correct 2230 ms 56644 KB Output is correct
9 Correct 5352 ms 76128 KB Output is correct
10 Correct 6898 ms 93768 KB Output is correct
11 Execution timed out 8070 ms 93532 KB Time limit exceeded
12 Correct 3168 ms 86388 KB Output is correct
13 Correct 4304 ms 86292 KB Output is correct
14 Correct 5594 ms 90312 KB Output is correct
15 Execution timed out 8026 ms 95652 KB Time limit exceeded
16 Execution timed out 8034 ms 99520 KB Time limit exceeded
17 Correct 7491 ms 97736 KB Output is correct