oj.uz

답안 #440155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440155 2021-07-01T16:29:16 Z dutch Regions (IOI09_regions) C++17
100 / 100
 5161 ms 35056 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 350;
 
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 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 += upper_bound(ord[y].begin(), ord[y].end(), t[u]+s[u]-1)
					 - lower_bound(ord[y].begin(), ord[y].end(), t[u]);
			}
			cout << ans << endl;
		}else{
			cout << res[x][y] << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10824 KB Output is correct
2 Correct 8 ms 10776 KB Output is correct
3 Correct 10 ms 10824 KB Output is correct
4 Correct 12 ms 10824 KB Output is correct
5 Correct 18 ms 10824 KB Output is correct
6 Correct 36 ms 10936 KB Output is correct
7 Correct 37 ms 10952 KB Output is correct
8 Correct 42 ms 10952 KB Output is correct
9 Correct 77 ms 11336 KB Output is correct
10 Correct 129 ms 11336 KB Output is correct
11 Correct 187 ms 11720 KB Output is correct
12 Correct 177 ms 12232 KB Output is correct
13 Correct 168 ms 11900 KB Output is correct
14 Correct 320 ms 12488 KB Output is correct
15 Correct 315 ms 15048 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2278 ms 15512 KB Output is correct
2 Correct 2707 ms 14360 KB Output is correct
3 Correct 3369 ms 17344 KB Output is correct
4 Correct 327 ms 12488 KB Output is correct
5 Correct 319 ms 14188 KB Output is correct
6 Correct 744 ms 15432 KB Output is correct
7 Correct 1536 ms 16228 KB Output is correct
8 Correct 1266 ms 23752 KB Output is correct
9 Correct 2729 ms 20288 KB Output is correct
10 Correct 3402 ms 35056 KB Output is correct
11 Correct 5161 ms 20176 KB Output is correct
12 Correct 1699 ms 21668 KB Output is correct
13 Correct 2428 ms 21868 KB Output is correct
14 Correct 3406 ms 23320 KB Output is correct
15 Correct 3621 ms 26084 KB Output is correct
16 Correct 3571 ms 31472 KB Output is correct
17 Correct 3226 ms 31936 KB Output is correct