Submission #321092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321092	2020-11-10T23:41:28 Z	super_j6	Regions (IOI09_regions)	C++14	35 / 100	7187 ms	40548 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, m = 450;
int n, k, q, t;
int a[mxn], b[mxn], p[mxn], dp[mxn], l[mxn], r[mxn], bit[mxn];
ll f1[m][mxn], f2[m][mxn];
vector<int> g[mxn], w[mxn];

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];
		cin >> a[i];
		g[--p[i]].push_back(i), w[--a[i]].push_back(i);
	}
	
	for(int i = 0; i < k; i++){
		if(w[i].size() > m){
			b[i] = t++;
			for(int j = 0; j < n; j++){
				f2[i][j] += (dp[j] = a[j] == i + (~p[j] ? dp[p[j]] : 0));
			}
			memset(dp, 0, sizeof(dp));
			for(int j = n - 1; ~j; j--){
				f1[i][j] += (dp[j] += a[j] == i);
				if(~p[j]) dp[p[j]] += dp[j];
	 		}
		}else{
			b[i] = -1;
		}
	}
	
	for(int i = 0; i < k; i++){
		
	}
	
	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	6 ms	9708 KB	Output is correct
2	Correct	7 ms	9836 KB	Output is correct
3	Correct	8 ms	9836 KB	Output is correct
4	Correct	11 ms	9836 KB	Output is correct
5	Correct	10 ms	9856 KB	Output is correct
6	Correct	22 ms	9776 KB	Output is correct
7	Correct	39 ms	9836 KB	Output is correct
8	Correct	41 ms	9964 KB	Output is correct
9	Correct	67 ms	10348 KB	Output is correct
10	Correct	102 ms	10476 KB	Output is correct
11	Correct	132 ms	10624 KB	Output is correct
12	Correct	167 ms	11244 KB	Output is correct
13	Correct	258 ms	10860 KB	Output is correct
14	Correct	411 ms	11372 KB	Output is correct
15	Correct	409 ms	14572 KB	Output is correct

Subtask #2

20.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1547 ms	34656 KB	Output isn't correct
2	Incorrect	1771 ms	30948 KB	Output isn't correct
3	Incorrect	3486 ms	32100 KB	Output isn't correct
4	Correct	399 ms	11500 KB	Output is correct
5	Correct	547 ms	13548 KB	Output is correct
6	Runtime error	62 ms	23556 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	92 ms	24808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	90 ms	37604 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	4013 ms	19428 KB	Output is correct
10	Runtime error	134 ms	27620 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Correct	7187 ms	19172 KB	Output is correct
12	Runtime error	147 ms	28004 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	143 ms	27492 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	125 ms	37860 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	146 ms	28900 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	148 ms	28900 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	124 ms	40548 KB	Execution killed with signal 11 (could be triggered by violating memory limits)