Submission #979857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
979857	2024-05-11T13:55:56 Z	Lib	Regions (IOI09_regions)	C++14	100 / 100	5468 ms	37872 KB

regions

#include <bits/stdc++.h>
using namespace std;
 //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	3 ms	9048 KB	Output is correct
2	Correct	2 ms	9048 KB	Output is correct
3	Correct	3 ms	9080 KB	Output is correct
4	Correct	5 ms	9596 KB	Output is correct
5	Correct	5 ms	9372 KB	Output is correct
6	Correct	12 ms	9928 KB	Output is correct
7	Correct	14 ms	9708 KB	Output is correct
8	Correct	20 ms	9992 KB	Output is correct
9	Correct	26 ms	10452 KB	Output is correct
10	Correct	55 ms	10468 KB	Output is correct
11	Correct	73 ms	11408 KB	Output is correct
12	Correct	91 ms	11668 KB	Output is correct
13	Correct	108 ms	11660 KB	Output is correct
14	Correct	166 ms	11560 KB	Output is correct
15	Correct	192 ms	14480 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	892 ms	15284 KB	Output is correct
2	Correct	895 ms	14400 KB	Output is correct
3	Correct	1384 ms	18460 KB	Output is correct
4	Correct	189 ms	12184 KB	Output is correct
5	Correct	259 ms	14788 KB	Output is correct
6	Correct	363 ms	13976 KB	Output is correct
7	Correct	507 ms	14432 KB	Output is correct
8	Correct	846 ms	21360 KB	Output is correct
9	Correct	1701 ms	24932 KB	Output is correct
10	Correct	3223 ms	30588 KB	Output is correct
11	Correct	2608 ms	26500 KB	Output is correct
12	Correct	3241 ms	23552 KB	Output is correct
13	Correct	3846 ms	24940 KB	Output is correct
14	Correct	4339 ms	25876 KB	Output is correct
15	Correct	5468 ms	32184 KB	Output is correct
16	Correct	5416 ms	37872 KB	Output is correct
17	Correct	4432 ms	36300 KB	Output is correct