oj.uz

답안 #660211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660211 2022-11-21T06:55:51 Z QwertyPi Regions (IOI09_regions) C++14
100 / 100
 5345 ms 34088 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;

const int N = 1 << 18;
const int LGN = 18;
const int R = 25001;
const int B = 500;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B][R], id[R], ids = 0;
vector<int> G[N];
vector<int> emp[N];
vector<int> pos[R];
int n, rn, q;

int ct = 0;
void dfs(int v){
	tl[v] = ++ct; preord[ct] = v;
	for(auto u : G[v]){
		dfs(u);
	}
	tr[v] = ct;
}

bool vis[N];
void dfs_prec(int Co, int v, int acc = 0){
	if(r[v] == Co) vis[v] = true;
	for(auto u : G[v]){
		dfs_prec(Co, u, acc + (r[v] == Co));
	}
	prec[id[Co]][r[v]] += acc;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> rn >> q;
	cin >> r[1];
	for(int i = 2; i <= n; i++){
		cin >> p[i] >> r[i];
		G[p[i]].push_back(i);
		cnt[r[i]]++;
	}
	for(int i = 1; i <= n; i++){
		emp[r[i]].push_back(i);
	}
	dfs(1);
	
	for(int i = 1; i <= rn; i++){
		if(cnt[i] >= B){
			id[i] = ids;
			ids++;
		}
	}

	for(int i = 1; i <= n; i++){
		if(cnt[r[i]] >= B && !vis[i]){
			dfs_prec(r[i], i);
		}
	}

	for(int i = 1; i <= n; i++){
		pos[r[preord[i]]].push_back(i);
	}
	
	for(int i = 0; i < q; i++){
		int r1, r2; cin >> r1 >> r2;
		if(cnt[r1] >= B){
			cout << prec[id[r1]][r2] << endl;
		}else{
			int ans = 0;
			for(auto i : emp[r1]){
				ans += upper_bound(pos[r2].begin(), pos[r2].end(), tr[i]) - lower_bound(pos[r2].begin(), pos[r2].end(), tl[i]);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13224 KB Output is correct
2 Correct 8 ms 13136 KB Output is correct
3 Correct 10 ms 13136 KB Output is correct
4 Correct 12 ms 13136 KB Output is correct
5 Correct 15 ms 13264 KB Output is correct
6 Correct 21 ms 13264 KB Output is correct
7 Correct 22 ms 13264 KB Output is correct
8 Correct 43 ms 13392 KB Output is correct
9 Correct 61 ms 13648 KB Output is correct
10 Correct 93 ms 13776 KB Output is correct
11 Correct 134 ms 14088 KB Output is correct
12 Correct 167 ms 14652 KB Output is correct
13 Correct 201 ms 14356 KB Output is correct
14 Correct 309 ms 15008 KB Output is correct
15 Correct 296 ms 16976 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1783 ms 18420 KB Output is correct
2 Correct 2431 ms 17460 KB Output is correct
3 Correct 2959 ms 20116 KB Output is correct
4 Correct 252 ms 15056 KB Output is correct
5 Correct 383 ms 16280 KB Output is correct
6 Correct 1162 ms 17172 KB Output is correct
7 Correct 2031 ms 17620 KB Output is correct
8 Correct 1493 ms 22316 KB Output is correct
9 Correct 2487 ms 23508 KB Output is correct
10 Correct 4438 ms 27472 KB Output is correct
11 Correct 5345 ms 24164 KB Output is correct
12 Correct 1770 ms 25712 KB Output is correct
13 Correct 2333 ms 25724 KB Output is correct
14 Correct 2796 ms 27572 KB Output is correct
15 Correct 3268 ms 29564 KB Output is correct
16 Correct 2907 ms 33288 KB Output is correct
17 Correct 2777 ms 34088 KB Output is correct