oj.uz

답안 #440166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440166 2021-07-01T16:43:15 Z dutch Regions (IOI09_regions) C++17
100 / 100
 5231 ms 31868 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 450;
 
int k[MAXN], cnt[MAXK], t[MAXN], s[MAXN], dfsTimer = 0, cur, c;
vector<int> g[MAXN], a[MAXN], res[MAXK], ord[MAXK];
 
void dfs0(int u){
	t[u] = dfsTimer++, s[u] = 1;
	ord[k[u]].push_back(t[u]);
	for(int v : g[u]) dfs0(v), s[u] += s[v];
}
 
void dfs1(int u){
	if(k[u] == cur) ++c;
	res[cur][k[u]] += c;
	for(int v : g[u]) dfs1(v);
	if(k[u] == cur) --c;
}

int bs(vector<int> &v, int val){
	int x = -1;
	for(int y=1<<15; y/=2; ) if(x+y < (int)v.size() && v[x+y] <= val) x += y;
	return x;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
 
	int n, r, q, x, y; cin >> n >> r >> q;
 
	for(int i=0, j; i<n; ++i){
		if(i) cin >> j, g[j-1].push_back(i);
		cin >> k[i], a[--k[i]].push_back(i);
	}
 
	dfs0(0);
 
	for(int i=0; i<r; ++i){
		if(a[i].size() < SQRT) continue;
		cur = i, c = 0;
		res[i].resize(r);
		dfs1(0);
	}
 
	while(q--){
		cin >> x >> y; --x, --y;
		if(a[x].size() < SQRT){
			int ans = 0;
			for(int u : a[x]){
				ans += bs(ord[y], t[u]+s[u]-1) - bs(ord[y], t[u]-1);
			}
			cout << ans << endl;
		}else{
			cout << res[x][y] << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10844 KB Output is correct
2 Correct 9 ms 10824 KB Output is correct
3 Correct 8 ms 10856 KB Output is correct
4 Correct 17 ms 10824 KB Output is correct
5 Correct 17 ms 10824 KB Output is correct
6 Correct 22 ms 10952 KB Output is correct
7 Correct 41 ms 11080 KB Output is correct
8 Correct 43 ms 10952 KB Output is correct
9 Correct 60 ms 11336 KB Output is correct
10 Correct 135 ms 11336 KB Output is correct
11 Correct 149 ms 11720 KB Output is correct
12 Correct 157 ms 12180 KB Output is correct
13 Correct 226 ms 11872 KB Output is correct
14 Correct 232 ms 12432 KB Output is correct
15 Correct 333 ms 15048 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1676 ms 15508 KB Output is correct
2 Correct 2050 ms 14356 KB Output is correct
3 Correct 2987 ms 17288 KB Output is correct
4 Correct 370 ms 12464 KB Output is correct
5 Correct 461 ms 14152 KB Output is correct
6 Correct 786 ms 15552 KB Output is correct
7 Correct 1544 ms 15400 KB Output is correct
8 Correct 1260 ms 23756 KB Output is correct
9 Correct 2975 ms 20232 KB Output is correct
10 Correct 4561 ms 30556 KB Output is correct
11 Correct 5231 ms 20172 KB Output is correct
12 Correct 1669 ms 21672 KB Output is correct
13 Correct 2186 ms 21860 KB Output is correct
14 Correct 3211 ms 23336 KB Output is correct
15 Correct 3638 ms 26080 KB Output is correct
16 Correct 4477 ms 31460 KB Output is correct
17 Correct 4226 ms 31868 KB Output is correct