Submission #321096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321096	2020-11-11T00:06:22 Z	super_j6	Regions (IOI09_regions)	C++14	100 / 100	7551 ms	45008 KB

regions

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
//#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 200001, mxk = 25000, m = 447;
int n, k, q, t;
int a[mxn], p[mxn], dp[mxn], l[mxn], r[mxn], bit[mxn], b[mxk];
ll f1[m][mxk], f2[m][mxk];
vector<int> g[mxn], w[mxk];

void add(int x, int v){
	for(x++; x <= n; x += x & -x) bit[x] += v;
}

int qry(int x){
	int ret = 0;
	for(x++; x; x -= x & -x) ret += bit[x];
	return ret;
}

int dfs(int c){
	r[c] = l[c];
	for(int i : g[c]) if(i != p[c]) l[i] = r[c] + 1, r[c] = dfs(i);
	return r[c];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> q;
	
	for(int i = 0; i < n; i++){
		if(i){
			cin >> p[i];
			g[--p[i]].push_back(i);
		}else{
			p[i] = -1;
		}
		cin >> a[i];
		w[--a[i]].push_back(i);
	}
	
	for(int i = 0; i < k; i++){
		if(w[i].size() > m){
			for(int j = 0; j < n; j++){
				f1[t][a[j]] += (dp[j] = (a[j] == i) + (~p[j] ? dp[p[j]] : 0));
			}
			memset(dp, 0, sizeof(dp));
			for(int j = n - 1; ~j; j--){
				f2[t][a[j]] += (dp[j] += a[j] == i);
				if(~p[j]) dp[p[j]] += dp[j];
	 		}
	 		b[i] = t++;
		}else{
			b[i] = -1;
		}
	}
	
	dfs(0);
	
	while(q--){
		int x, y;
		cin >> x >> y;
		x--, y--;
		if(~b[x]){
			cout << f1[b[x]][y] << endl;
		}else if(~b[y]){
			cout << f2[b[y]][x] << endl;
		}else{
			ll ret = 0;
			for(int i : w[y]) add(l[i], 1);
			for(int i : w[x]) ret += qry(r[i]) - qry(l[i] - 1);
			for(int i : w[y]) add(l[i], -1);
			cout << ret << endl;
		}
	}

	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5612 KB	Output is correct
2	Correct	4 ms	5612 KB	Output is correct
3	Correct	4 ms	5612 KB	Output is correct
4	Correct	6 ms	5612 KB	Output is correct
5	Correct	11 ms	5740 KB	Output is correct
6	Correct	15 ms	5740 KB	Output is correct
7	Correct	32 ms	5740 KB	Output is correct
8	Correct	25 ms	5740 KB	Output is correct
9	Correct	55 ms	6252 KB	Output is correct
10	Correct	94 ms	6252 KB	Output is correct
11	Correct	149 ms	6508 KB	Output is correct
12	Correct	168 ms	7148 KB	Output is correct
13	Correct	247 ms	6636 KB	Output is correct
14	Correct	362 ms	7276 KB	Output is correct
15	Correct	405 ms	10604 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1595 ms	11620 KB	Output is correct
2	Correct	1659 ms	10400 KB	Output is correct
3	Correct	3322 ms	13924 KB	Output is correct
4	Correct	400 ms	7404 KB	Output is correct
5	Correct	427 ms	9452 KB	Output is correct
6	Correct	533 ms	16612 KB	Output is correct
7	Correct	2083 ms	13156 KB	Output is correct
8	Correct	1132 ms	32996 KB	Output is correct
9	Correct	4147 ms	15588 KB	Output is correct
10	Correct	4349 ms	45008 KB	Output is correct
11	Correct	7551 ms	15076 KB	Output is correct
12	Correct	2137 ms	18020 KB	Output is correct
13	Correct	2723 ms	18404 KB	Output is correct
14	Correct	2800 ms	24548 KB	Output is correct
15	Correct	5499 ms	23392 KB	Output is correct
16	Correct	5687 ms	30844 KB	Output is correct
17	Correct	4513 ms	35812 KB	Output is correct