oj.uz

답안 #321096

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321096 2020-11-11T00:06:22 Z super_j6 Regions (IOI09_regions) C++14
100 / 100
 7551 ms 45008 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, 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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