oj.uz

답안 #206501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206501 2020-03-03T13:23:42 Z jhnah917 Regions (IOI09_regions) C++14
100 / 100
 4847 ms 35780 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int n, r, q;
int arr[202020];
vector<int> g[202020];

int in[202020], pv;
int sz[202020];
vector<int> g1[25252], g2[25252];

map<p, int> mp;

int dfs(int v){
	in[v] = ++pv; sz[in[v]] = 1;
	g1[arr[v]].push_back(in[v]);
	for(auto i : g[v]){
		sz[in[v]] += dfs(i);
	}
	g2[arr[v]].push_back(pv);
	return sz[in[v]];
}

int q1(int a, int b){
	int ret = 0;
	for(auto i : g1[a]){
		int x = lower_bound(all(g1[b]), i + sz[i]) - g1[b].begin();
		int y = lower_bound(all(g1[b]), i) - g1[b].begin();
		ret += x - y;
	}
	return ret;
}

int q2(int a, int b){
	int ret = 0;
	for(auto i : g1[b]){
		int x = upper_bound(all(g1[a]), i) - g1[a].begin();
		int y = lower_bound(all(g2[a]), i) - g2[a].begin();
		ret += x - y;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> r >> q;
	cin >> arr[1];
	for(int i=2; i<=n; i++){
		int t; cin >> t >> arr[i];
		g[t].push_back(i);
	}
	dfs(1);
	for(int i=0; i<25252; i++) sort(all(g2[i]));

	while(q--){
		int a, b; cin >> a >> b;
		if(mp.find({a, b}) != mp.end()){
			cout << mp[{a, b}] << endl; continue;
		}
		int ans;
		if(g1[a].size() < g1[b].size()) ans = mp[{a, b}] = q1(a, b);
		else ans = mp[{a, b}] = q2(a, b);
		cout << ans << endl;
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 9 ms 6264 KB Output is correct
3 Correct 10 ms 6264 KB Output is correct
4 Correct 12 ms 6264 KB Output is correct
5 Correct 15 ms 6392 KB Output is correct
6 Correct 28 ms 6520 KB Output is correct
7 Correct 37 ms 6520 KB Output is correct
8 Correct 43 ms 6540 KB Output is correct
9 Correct 59 ms 7032 KB Output is correct
10 Correct 77 ms 7244 KB Output is correct
11 Correct 126 ms 7620 KB Output is correct
12 Correct 117 ms 8260 KB Output is correct
13 Correct 179 ms 7980 KB Output is correct
14 Correct 264 ms 8568 KB Output is correct
15 Correct 278 ms 10652 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1257 ms 12612 KB Output is correct
2 Correct 1458 ms 11480 KB Output is correct
3 Correct 1990 ms 16036 KB Output is correct
4 Correct 253 ms 9592 KB Output is correct
5 Correct 365 ms 11256 KB Output is correct
6 Correct 568 ms 11232 KB Output is correct
7 Correct 798 ms 11388 KB Output is correct
8 Correct 1101 ms 18236 KB Output is correct
9 Correct 2152 ms 23612 KB Output is correct
10 Correct 3975 ms 29500 KB Output is correct
11 Correct 4847 ms 27444 KB Output is correct
12 Correct 1616 ms 22072 KB Output is correct
13 Correct 2281 ms 24164 KB Output is correct
14 Correct 2632 ms 25340 KB Output is correct
15 Correct 3512 ms 31640 KB Output is correct
16 Correct 3418 ms 35780 KB Output is correct
17 Correct 3607 ms 34272 KB Output is correct