oj.uz

답안 #321095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321095 2020-11-11T00:04:08 Z super_j6 Regions (IOI09_regions) C++14
100 / 100
 7748 ms 43364 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 = 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

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

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