Submission #321095

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321095	2020-11-11T00:04:08 Z	super_j6	Regions (IOI09_regions)	C++14	100 / 100	7748 ms	43364 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 = 449;
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	6 ms	5612 KB	Output is correct
4	Correct	8 ms	5632 KB	Output is correct
5	Correct	11 ms	5868 KB	Output is correct
6	Correct	23 ms	5740 KB	Output is correct
7	Correct	33 ms	5760 KB	Output is correct
8	Correct	27 ms	5740 KB	Output is correct
9	Correct	58 ms	6272 KB	Output is correct
10	Correct	68 ms	6352 KB	Output is correct
11	Correct	147 ms	6508 KB	Output is correct
12	Correct	165 ms	7148 KB	Output is correct
13	Correct	219 ms	6636 KB	Output is correct
14	Correct	395 ms	7276 KB	Output is correct
15	Correct	451 ms	10452 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1431 ms	11652 KB	Output is correct
2	Correct	1778 ms	10340 KB	Output is correct
3	Correct	3166 ms	13796 KB	Output is correct
4	Correct	378 ms	7404 KB	Output is correct
5	Correct	477 ms	9452 KB	Output is correct
6	Correct	479 ms	16612 KB	Output is correct
7	Correct	2230 ms	12772 KB	Output is correct
8	Correct	1213 ms	33124 KB	Output is correct
9	Correct	4254 ms	15460 KB	Output is correct
10	Correct	4857 ms	43364 KB	Output is correct
11	Correct	7748 ms	15052 KB	Output is correct
12	Correct	2045 ms	18020 KB	Output is correct
13	Correct	2804 ms	18532 KB	Output is correct
14	Correct	3153 ms	24548 KB	Output is correct
15	Correct	5242 ms	23436 KB	Output is correct
16	Correct	6030 ms	30820 KB	Output is correct
17	Correct	4531 ms	35832 KB	Output is correct