oj.uz

Submission #528957

# Submission time Handle Problem Language Result Execution time Memory
528957 2022-02-21T20:36:15 Z kevinyang Regions (IOI09_regions) C++14
0 / 100
 23 ms 29072 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 Runtime error 18 ms 29000 KB Execution killed with signal 6
2 Runtime error 17 ms 28984 KB Execution killed with signal 6
3 Runtime error 17 ms 28952 KB Execution killed with signal 6
4 Runtime error 17 ms 28956 KB Execution killed with signal 6
5 Runtime error 19 ms 29064 KB Execution killed with signal 6
6 Runtime error 17 ms 29000 KB Execution killed with signal 6
7 Runtime error 17 ms 28984 KB Execution killed with signal 6
8 Runtime error 18 ms 29000 KB Execution killed with signal 6
9 Runtime error 17 ms 28992 KB Execution killed with signal 6
10 Runtime error 17 ms 29000 KB Execution killed with signal 6
11 Runtime error 17 ms 29000 KB Execution killed with signal 6
12 Runtime error 17 ms 29072 KB Execution killed with signal 6
13 Runtime error 17 ms 29008 KB Execution killed with signal 6
14 Runtime error 17 ms 28952 KB Execution killed with signal 6
15 Runtime error 17 ms 29008 KB Execution killed with signal 6

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 28992 KB Execution killed with signal 6
2 Runtime error 17 ms 28980 KB Execution killed with signal 6
3 Runtime error 17 ms 28980 KB Execution killed with signal 6
4 Runtime error 18 ms 29000 KB Execution killed with signal 6
5 Runtime error 18 ms 28988 KB Execution killed with signal 6
6 Runtime error 18 ms 28996 KB Execution killed with signal 6
7 Runtime error 18 ms 29052 KB Execution killed with signal 6
8 Runtime error 17 ms 28996 KB Execution killed with signal 6
9 Runtime error 18 ms 29000 KB Execution killed with signal 6
10 Runtime error 19 ms 28980 KB Execution killed with signal 6
11 Runtime error 23 ms 28996 KB Execution killed with signal 6
12 Runtime error 18 ms 28992 KB Execution killed with signal 6
13 Runtime error 18 ms 29000 KB Execution killed with signal 6
14 Runtime error 18 ms 29004 KB Execution killed with signal 6
15 Runtime error 18 ms 28996 KB Execution killed with signal 6
16 Runtime error 17 ms 29000 KB Execution killed with signal 6
17 Runtime error 17 ms 28992 KB Execution killed with signal 6