oj.uz

답안 #660202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660202 2022-11-21T06:11:04 Z QwertyPi Regions (IOI09_regions) C++14
75 / 100
 8000 ms 122312 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 11;
const int LGN = 20;
const int R = 2.5e4 + 11;
const int B = 400;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B + 10][R], id[R], ids = 0;
int prec2[R][N / B + 10], id2[R], ids2 = 0;
vector<int> G[N];
vector<int> emp[N];
int n, rn, q;

int ct = 0;
void dfs(int v){
	tl[v] = ++ct; preord[ct] = v;
	for(auto u : G[v]){
		dfs(u);
	}
	tr[v] = ct;
}
void dfs_prec(int Co, int v, int acc = 0){
	for(auto u : G[v]){
		dfs_prec(Co, u, acc + (r[v] == Co));
	}
	prec[id[Co]][r[v]] += acc;
}

int dfs_prec2(int Co, int v){
	int acc = r[v] == Co;
	for(auto u : G[v]){
		acc += dfs_prec2(Co, u);
	}
	prec2[r[v]][id2[Co]] += acc;
	return acc;
}

namespace DS{
	int a[N] = {}, roots[N];
	int t[N * LGN * 8] = {};
	int lch[N * LGN * 8] = {};
	int rch[N * LGN * 8] = {};
	int cc = 0;
	
	int build(int rt, int l, int r){
		if(l == r) return rt;
		int m = (l + r) / 2;
		int lc = build(++cc, l, m);
		int rc = build(++cc, m + 1, r);
		lch[rt] = lc, rch[rt] = rc;
		return rt;
	}

	int add(int qi, int qv, int rt, int l, int r){
		if(l == r) { t[++cc] = t[rt] + qv; return cc; }
		int m = (l + r) / 2;
		if(qi <= m){
			int lc = add(qi, qv, lch[rt], l, m);
			int rc = rch[rt];
			lch[++cc] = lc, rch[cc] = rc;
		}else{
			int lc = lch[rt];
			int rc = add(qi, qv, rch[rt], m + 1, r);
			lch[++cc] = lc, rch[cc] = rc;
		}
		return cc;
	}

	int qry(int qi, int rt, int l, int r){
		if(l == r) return t[rt];
		int m = (l + r) / 2;
		if(qi <= m) return qry(qi, lch[rt], l, m);
		return qry(qi, rch[rt], m + 1, r);
	}
	
	void init(int n){
		for(int i = 1; i <= n; i++){
			a[i] = r[preord[i]];
		}
		roots[0] = build(0, 1, rn);
		for(int i = 1; i <= n; i++){
			roots[i] = add(a[i], 1, roots[i - 1], 1, rn);
		}
	}
};

int qry(int _l, int _r, int v){
	return DS::qry(v, DS::roots[_r], 1, rn) - DS::qry(v, DS::roots[_l - 1], 1, rn);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> rn >> q;
	cin >> r[1];
	for(int i = 2; i <= n; i++){
		cin >> p[i] >> r[i];
		G[p[i]].push_back(i);
		cnt[r[i]]++;
	}
	for(int i = 1; i <= n; i++){
		emp[r[i]].push_back(i);
	}
	dfs(1);
	for(int i = 1; i <= rn; i++){
		if(cnt[i] >= B){
			id[i] = ids;
			dfs_prec(i, 1);
			ids++;
		}
	}

	for(int i = 1; i <= rn; i++){
		if(cnt[i] >= B){
			id2[i] = ids2;
			dfs_prec2(i, 1);
			ids2++;
		}
	}
	
	DS::init(n);
	
	for(int i = 0; i < q; i++){
		int r1, r2; cin >> r1 >> r2;
		if(cnt[r1] >= B){
			cout << prec[id[r1]][r2] << endl;
		}else if(cnt[r2] >= B){
			cout << prec2[r1][id2[r2]] << endl;
		}else{
			int ans = 0;
			for(auto i : emp[r1]){
				ans += qry(tl[i], tr[i], r2);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9680 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 7 ms 9680 KB Output is correct
5 Correct 8 ms 9740 KB Output is correct
6 Correct 22 ms 9884 KB Output is correct
7 Correct 28 ms 9936 KB Output is correct
8 Correct 37 ms 10064 KB Output is correct
9 Correct 46 ms 10832 KB Output is correct
10 Correct 83 ms 11580 KB Output is correct
11 Correct 138 ms 12368 KB Output is correct
12 Correct 158 ms 13636 KB Output is correct
13 Correct 222 ms 13592 KB Output is correct
14 Correct 291 ms 14724 KB Output is correct
15 Correct 398 ms 17872 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1730 ms 23652 KB Output is correct
2 Correct 1846 ms 22940 KB Output is correct
3 Correct 3857 ms 27844 KB Output is correct
4 Correct 424 ms 16232 KB Output is correct
5 Correct 538 ms 18768 KB Output is correct
6 Correct 725 ms 37440 KB Output is correct
7 Correct 2672 ms 47568 KB Output is correct
8 Correct 2001 ms 62024 KB Output is correct
9 Execution timed out 8035 ms 46536 KB Time limit exceeded
10 Correct 6783 ms 118396 KB Output is correct
11 Execution timed out 8006 ms 57864 KB Time limit exceeded
12 Correct 4917 ms 87656 KB Output is correct
13 Correct 7169 ms 88136 KB Output is correct
14 Correct 6912 ms 99796 KB Output is correct
15 Execution timed out 8032 ms 115064 KB Time limit exceeded
16 Execution timed out 8036 ms 122312 KB Time limit exceeded
17 Execution timed out 8080 ms 110800 KB Time limit exceeded