oj.uz

Submission #754364

# Submission time Handle Problem Language Result Execution time Memory
754364 2023-06-07T14:58:19 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=200;
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 10320 KB Output is correct
2 Correct 8 ms 10320 KB Output is correct
3 Correct 6 ms 10384 KB Output is correct
4 Correct 14 ms 10376 KB Output is correct
5 Correct 12 ms 10496 KB Output is correct
6 Correct 14 ms 10704 KB Output is correct
7 Correct 29 ms 10880 KB Output is correct
8 Correct 52 ms 10924 KB Output is correct
9 Correct 68 ms 12364 KB Output is correct
10 Correct 121 ms 13904 KB Output is correct
11 Correct 219 ms 15372 KB Output is correct
12 Correct 299 ms 17804 KB Output is correct
13 Correct 307 ms 18304 KB Output is correct
14 Correct 496 ms 20004 KB Output is correct
15 Correct 809 ms 26112 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2779 ms 32492 KB Output is correct
2 Correct 1414 ms 32632 KB Output is correct
3 Execution timed out 8020 ms 38980 KB Time limit exceeded
4 Correct 467 ms 22404 KB Output is correct
5 Correct 677 ms 26984 KB Output is correct
6 Correct 974 ms 32732 KB Output is correct
7 Correct 1691 ms 43828 KB Output is correct
8 Correct 1707 ms 58600 KB Output is correct
9 Correct 4070 ms 82960 KB Output is correct
10 Correct 4729 ms 121808 KB Output is correct
11 Runtime error 4696 ms 131072 KB Execution killed with signal 9
12 Correct 7320 ms 105720 KB Output is correct
13 Correct 5336 ms 106488 KB Output is correct
14 Correct 3611 ms 90572 KB Output is correct
15 Correct 6576 ms 97772 KB Output is correct
16 Runtime error 1148 ms 131072 KB Execution killed with signal 9
17 Correct 6153 ms 102592 KB Output is correct