oj.uz

Submission #321093

# Submission time Handle Problem Language Result Execution time Memory
321093 2020-11-10T23:44:52 Z super_j6 Regions (IOI09_regions) C++14
35 / 100
 7304 ms 40552 KB 
#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];
			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){
			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 9836 KB Output is correct
2 Correct 6 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 13 ms 9836 KB Output is correct
6 Correct 17 ms 9932 KB Output is correct
7 Correct 37 ms 9836 KB Output is correct
8 Correct 39 ms 9964 KB Output is correct
9 Correct 59 ms 10348 KB Output is correct
10 Correct 103 ms 10348 KB Output is correct
11 Correct 143 ms 10604 KB Output is correct
12 Correct 167 ms 11244 KB Output is correct
13 Correct 231 ms 10860 KB Output is correct
14 Correct 373 ms 11372 KB Output is correct
15 Correct 487 ms 14572 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1653 ms 34916 KB Output isn't correct
2 Incorrect 1879 ms 30820 KB Output isn't correct
3 Incorrect 3285 ms 31972 KB Output isn't correct
4 Correct 409 ms 11500 KB Output is correct
5 Correct 417 ms 13676 KB Output is correct
6 Runtime error 63 ms 23788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 88 ms 24804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 89 ms 37604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 4014 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 7304 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 145 ms 27492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 140 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 151 ms 28772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 129 ms 40552 KB Execution killed with signal 11 (could be triggered by violating memory limits)