oj.uz

답안 #1082422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1082422 2024-08-31T10:15:01 Z Thunnus Regions (IOI09_regions) C++17
100 / 100
 2632 ms 47748 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size() 

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, r, q;
	cin >> n >> r >> q;
	const int SZ = ceil(sqrt(n));
	vi par(n), reg(n);
	vvi children(n), precalc(r), reg_tins(r), r2v(r);
	cin >> reg[0];
	reg[0]--;
	for(int i = 1; i < n; i++){
		cin >> par[i] >> reg[i];
		par[i]--, reg[i]--;
		children[par[i]].emplace_back(i);
	}

	vi tin(n), tout(n);
	int timer = 0;
	function<void(int)> euler = [&](int v) -> void {
		tin[v] = timer++;
		reg_tins[reg[v]].emplace_back(tin[v]);
		r2v[reg[v]].emplace_back(v);
		for(int &u : children[v]){
			euler(u);
		}
		tout[v] = timer - 1;
	};
	euler(0);

	int curreg = -1, curcnt = 0;
	function<void(int)> dfs = [&](int v) -> void {
		if(curreg == reg[v]){
			curcnt++;
		}
		else{
			precalc[curreg][reg[v]] += curcnt;
		}
		for(int &u : children[v]){
			dfs(u);
		}
		curcnt -= (curreg == reg[v]);
	};

	for(int i = 0; i < r; i++){
		if(sz(r2v[i]) >= SZ){
			curreg = i, curcnt = 0;
			precalc[i].resize(r);
			dfs(0);
		}
	}

	while(q--){
		int r1, r2;
		cin >> r1 >> r2;
		r1--, r2--;
		if(sz(r2v[r1]) >= SZ){
			cout << precalc[r1][r2] << endl;
		}
		else{
			int ans = 0;
			for(int &v : r2v[r1]){
				ans += upper_bound(reg_tins[r2].begin(), reg_tins[r2].end(), tout[v]) - lower_bound(reg_tins[r2].begin(), reg_tins[r2].end(), tin[v]);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 13 ms 600 KB Output is correct
7 Correct 14 ms 600 KB Output is correct
8 Correct 18 ms 764 KB Output is correct
9 Correct 29 ms 1368 KB Output is correct
10 Correct 44 ms 1368 KB Output is correct
11 Correct 69 ms 2136 KB Output is correct
12 Correct 95 ms 3072 KB Output is correct
13 Correct 109 ms 2932 KB Output is correct
14 Correct 169 ms 3852 KB Output is correct
15 Correct 179 ms 8140 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1460 ms 9640 KB Output is correct
2 Correct 1637 ms 8536 KB Output is correct
3 Correct 2281 ms 12888 KB Output is correct
4 Correct 190 ms 4144 KB Output is correct
5 Correct 282 ms 6844 KB Output is correct
6 Correct 458 ms 10136 KB Output is correct
7 Correct 941 ms 13132 KB Output is correct
8 Correct 893 ms 25244 KB Output is correct
9 Correct 1663 ms 19908 KB Output is correct
10 Correct 2400 ms 47748 KB Output is correct
11 Correct 2632 ms 22624 KB Output is correct
12 Correct 957 ms 22632 KB Output is correct
13 Correct 1370 ms 23400 KB Output is correct
14 Correct 1771 ms 26956 KB Output is correct
15 Correct 2467 ms 30044 KB Output is correct
16 Correct 2495 ms 38768 KB Output is correct
17 Correct 2387 ms 40472 KB Output is correct