oj.uz

답안 #660206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660206 2022-11-21T06:32:54 Z QwertyPi Regions (IOI09_regions) C++14
90 / 100
 8000 ms 126520 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;

const int N = 1 << 18;
const int LGN = 18;
const int R = 1 << 15;
const int B = 128;
int p[N], r[N];
int tl[N], tr[N], preord[N], cnt[R];
int prec[N / B][R], id[R], ids = 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;
}

namespace DS{
	int a[N] = {}, roots[N];
	int t[N * LGN * 4] = {};
	int lch[N * LGN * 4] = {};
	int rch[N * LGN * 4] = {};
	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){
		while(l != r){
			int m = (l + r) / 2;
			if(qi <= m) rt = lch[rt], r = m;
			else rt = rch[rt], l = m + 1;
		}
		return t[rt];
	}
	
	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++;
		}
	}

	DS::init(n);
	for(int i = 1; i <= n; i++){
		G[i].clear();
	}
	
	for(int i = 0; i < q; i++){
		int r1, r2; cin >> r1 >> r2;
		if(cnt[r1] >= B){
			cout << prec[id[r1]][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 7 ms 12624 KB Output is correct
2 Correct 7 ms 12632 KB Output is correct
3 Correct 8 ms 12624 KB Output is correct
4 Correct 11 ms 12688 KB Output is correct
5 Correct 15 ms 12752 KB Output is correct
6 Correct 25 ms 12796 KB Output is correct
7 Correct 33 ms 12880 KB Output is correct
8 Correct 30 ms 13008 KB Output is correct
9 Correct 48 ms 13648 KB Output is correct
10 Correct 93 ms 14416 KB Output is correct
11 Correct 134 ms 15184 KB Output is correct
12 Correct 147 ms 16372 KB Output is correct
13 Correct 217 ms 16488 KB Output is correct
14 Correct 289 ms 18388 KB Output is correct
15 Correct 265 ms 21840 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 947 ms 26400 KB Output is correct
2 Correct 1107 ms 26036 KB Output is correct
3 Correct 1444 ms 30332 KB Output is correct
4 Correct 327 ms 21144 KB Output is correct
5 Correct 503 ms 21764 KB Output is correct
6 Correct 663 ms 26456 KB Output is correct
7 Correct 1210 ms 33004 KB Output is correct
8 Correct 2078 ms 43136 KB Output is correct
9 Correct 6302 ms 88236 KB Output is correct
10 Correct 2951 ms 119436 KB Output is correct
11 Correct 6896 ms 121144 KB Output is correct
12 Execution timed out 8085 ms 62496 KB Time limit exceeded
13 Correct 6542 ms 99896 KB Output is correct
14 Execution timed out 8048 ms 103308 KB Time limit exceeded
15 Correct 3864 ms 126520 KB Output is correct
16 Correct 3634 ms 120324 KB Output is correct
17 Correct 3441 ms 110020 KB Output is correct