Submission #206501

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
206501	2020-03-03T13:23:42 Z	jhnah917	Regions (IOI09_regions)	C++14	100 / 100	4847 ms	35780 KB

regions

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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