제출 #979858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979858		Lib	Regions (IOI09_regions)	C++14	100 / 100	5211 ms	38552 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O2","Ofast")
 //Stolen from KamiLeon as a proof of concept. Will try to do something properly later
void just_do_it();
 
int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}
 
const int maxn = 2e5 + 20;
const int maxk = 2.5e4 + 20;
int a[maxn];
int sz[maxk];
vector<int> nodes[maxk];
vector<int> times[maxk];
vector<int> ch[maxn];
int tin[maxn];
int tout[maxn];
map<int, int> memo[maxk];
int n, k, q, t;
 
void dfs(int u) {
	tin[u] = ++t;
	nodes[a[u]].push_back(u);
	times[a[u]].push_back(tin[u]);
	for (auto v: ch[u]) {
		dfs(v);
	}
	tout[u] = t;
}
 
int query(int x, int y) {
  	if(sz[y]<sz[x]){
      swap(x,y);
    }
	auto it = memo[x].find(y);
	if (it != memo[x].end()) {
		return it->second;
	}
	int res = 0;
	for (auto u: nodes[x]) {
		res += upper_bound(times[y].begin(), times[y].end(), tout[u]) - lower_bound(times[y].begin(), times[y].end(), tin[u]);
	}
	return (memo[x][y] = res);
}
 
void just_do_it() {
	cin >> n >> k >> q;
	cin >> a[1];
	for (int v = 2; v <= n; v++) {
		int u;
		cin >> u >> a[v];
		ch[u].push_back(v);
	}
  	for(int i=1;i<=k;i++){
      sz[i]=times[i].size();
    }
	dfs(1);
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		cout << query(x, y) << endl;
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85