oj.uz

Submission #528958

# Submission time Handle Problem Language Result Execution time Memory
528958 2022-02-21T20:36:59 Z kevinyang Regions (IOI09_regions) C++14
0 / 100
 1127 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 200005;
vector<int>h(mxn);
vector<vector<int>>reg(mxn);
vector<vector<int>>adj(mxn);
vector<int>sz(mxn);
vector<int>loc(mxn);
int timer = 0;
struct BIT{
	vector<int>arr;
	int size;
	void init(int n){
		size = n;
		arr.resize(n+5);
	}
	void update(int x, int val){
		assert(x!=0);
		for(int a = x; a<=size; a+=a&-a){
			arr[a]+=val;
		}
	}
	int query(int x){
		int sum = 0;
		for(int a = x; a>0; a-=a&-a){
			sum+=arr[a];
		}
		return sum;
	}
	void change(int x, int val){
		int v = query(x)-query(x-1);
		update(x,val-v);
	}
	int query(int x, int y){//inclusive
		return query(y)-query(x-1);
	}
};
void dfs(int u, int p){
	sz[u] = 1; timer++;
	loc[u] = timer;
	for(int nxt: adj[u]){
		if(nxt==p)continue;
		dfs(nxt,u);
		sz[u]+=sz[nxt];
	}
}
set<pair<int,int>>st;
map<pair<int,int>,int>hm;
const int sq = 200;
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,r,q;
	cin >> n >> r >> q;
	//assert(n==6&&r==3&&q==4);
	cin >> h[1];
	reg[h[1]].push_back(1);
	for(int i = 2; i<=n; i++){
		int x;
		cin >> x;
		cin >> h[i];
		reg[h[i]].push_back(i);
		adj[x].push_back(i);
		adj[i].push_back(x);
	}
	//assert(r<=500);
	dfs(1,0);
	BIT bit;
	BIT bit2;
	bit.init(mxn);
	bit2.init(mxn);
	for(int t = 1; t<=r; t++){
		if(reg[t].size()>=sq){
			for(int nxt: reg[t]){
				bit.update(loc[nxt],1);
				bit2.update(loc[nxt],1);
				bit2.update(loc[nxt]+sz[nxt],-1);
			}
			for(int u = t+1; u<=r; u++){
				int sum = 0;//u is ancestor
				int sum2 = 0;//u is child
				if(u==t)continue;
				for(int nxt: reg[u]){
					sum+=bit.query(loc[nxt],loc[nxt]+sz[nxt]-1);
					sum2+=bit2.query(loc[nxt]);
				}
				st.insert({t,u});
				st.insert({u,t});
				hm[{u,t}] = sum;
				hm[{t,u}] = sum2;
			}
			for(int nxt: reg[t]){
				bit.update(loc[nxt],-1);
				bit2.update(loc[nxt],-1);
				bit2.update(loc[nxt]+sz[nxt],1);
			}
		}
	}
	for(int t = 0; t<q; t++){
		int u,v;
		cin >> u >> v;
		if(st.find({u,v})==st.end()){
			assert(reg[v].size()<=sq);
			assert(reg[u].size()<=sq);
			for(int nxt: reg[v]){
				bit.update(loc[nxt],1);
			}
			int sum = 0;
			for(int nxt: reg[u]){
				sum+=bit.query(loc[nxt],loc[nxt]+sz[nxt]-1);
			}
			cout << sum << "\n";
			for(int nxt: reg[v]){
				bit.update(loc[nxt],-1);
			}
			
		}
		else{
			cout << hm[{u,v}] << "\n";
		}
		//if(t==0)assert(false);
	}
	//assert(false);
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8 ms 17480 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 17480 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 17480 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 17480 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 17480 KB Time limit exceeded (wall clock)
6 Execution timed out 8 ms 17608 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 17560 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 17608 KB Time limit exceeded (wall clock)
9 Execution timed out 9 ms 17992 KB Time limit exceeded (wall clock)
10 Execution timed out 11 ms 17992 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 18120 KB Time limit exceeded (wall clock)
12 Execution timed out 13 ms 18632 KB Time limit exceeded (wall clock)
13 Execution timed out 14 ms 18696 KB Time limit exceeded (wall clock)
14 Execution timed out 19 ms 19016 KB Time limit exceeded (wall clock)
15 Execution timed out 18 ms 21832 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 253 ms 48832 KB Execution killed with signal 6
2 Execution timed out 366 ms 25584 KB Time limit exceeded (wall clock)
3 Execution timed out 624 ms 31792 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 19092 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 20680 KB Time limit exceeded (wall clock)
6 Execution timed out 430 ms 76076 KB Time limit exceeded (wall clock)
7 Execution timed out 575 ms 96576 KB Time limit exceeded (wall clock)
8 Runtime error 970 ms 131076 KB Execution killed with signal 9
9 Runtime error 1109 ms 131076 KB Execution killed with signal 9
10 Runtime error 869 ms 131076 KB Execution killed with signal 9
11 Runtime error 1010 ms 131076 KB Execution killed with signal 9
12 Runtime error 1127 ms 131076 KB Execution killed with signal 9
13 Runtime error 1123 ms 131076 KB Execution killed with signal 9
14 Execution timed out 993 ms 121472 KB Time limit exceeded (wall clock)
15 Execution timed out 107 ms 34404 KB Time limit exceeded (wall clock)
16 Runtime error 866 ms 131076 KB Execution killed with signal 9
17 Runtime error 934 ms 131076 KB Execution killed with signal 9