oj.uz

Submission #979858

# Submission time Handle Problem Language Result Execution time Memory
979858 2024-05-11T13:58:06 Z Lib Regions (IOI09_regions) C++14
100 / 100
 5211 ms 38552 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9048 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 3 ms 9076 KB Output is correct
4 Correct 4 ms 9344 KB Output is correct
5 Correct 6 ms 9108 KB Output is correct
6 Correct 9 ms 9676 KB Output is correct
7 Correct 14 ms 9492 KB Output is correct
8 Correct 16 ms 9968 KB Output is correct
9 Correct 28 ms 10600 KB Output is correct
10 Correct 47 ms 10912 KB Output is correct
11 Correct 69 ms 11400 KB Output is correct
12 Correct 90 ms 11640 KB Output is correct
13 Correct 111 ms 11812 KB Output is correct
14 Correct 141 ms 12040 KB Output is correct
15 Correct 193 ms 14164 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 15316 KB Output is correct
2 Correct 932 ms 14880 KB Output is correct
3 Correct 1501 ms 18932 KB Output is correct
4 Correct 188 ms 12808 KB Output is correct
5 Correct 244 ms 15080 KB Output is correct
6 Correct 376 ms 14272 KB Output is correct
7 Correct 528 ms 14632 KB Output is correct
8 Correct 820 ms 20780 KB Output is correct
9 Correct 1580 ms 24020 KB Output is correct
10 Correct 3411 ms 30672 KB Output is correct
11 Correct 2977 ms 26896 KB Output is correct
12 Correct 3110 ms 23364 KB Output is correct
13 Correct 3887 ms 24700 KB Output is correct
14 Correct 4547 ms 25824 KB Output is correct
15 Correct 5211 ms 31888 KB Output is correct
16 Correct 4887 ms 38552 KB Output is correct
17 Correct 4352 ms 36500 KB Output is correct