oj.uz

답안 #979857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979857 2024-05-11T13:55:56 Z Lib Regions (IOI09_regions) C++14
100 / 100
 5468 ms 37872 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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