oj.uz

답안 #378846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378846 2021-03-17T06:02:28 Z 8e7 Regions (IOI09_regions) C++14
100 / 100
 7201 ms 32108 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 200005
#define maxc 25005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> adj[maxn], pos[maxc], node[maxc];
int col[maxn], cnt[maxc], ind[1000], cor[maxc];

int ans[705][maxc], lef[maxn], rig[maxn];

int cur = 0, num = 0, c = 0;
void dfs(int n, int par) {
	lef[n] = c++;
	ans[cur][col[n]] += num;
	if (col[n] == ind[cur]) num++;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
		}
	}
	rig[n] = c;
	if (col[n] == ind[cur]) num--;
}
int main() {
	io
	int n, r, q;
	cin >> n >> r >> q;
	cin >> col[1];
	cnt[col[1]]++;
	node[col[1]].push_back(1);
	for (int i = 2;i <= n;i++) {
		int p;
		cin >> p >> col[i];
		adj[p].push_back(i);
		adj[i].push_back(p);
		node[col[i]].push_back(i);
		cnt[col[i]]++;
	}
	dfs(1, 0);
	int id = 0;
	for (int i = 1;i <= r;i++) {
		if (cnt[i] >= 300) {
			ind[id] = i;
			cor[i] = id;
			cur = id;
			c = 0;
			dfs(1, 0);
			id++;
		}
	}
	for (int i = 1;i <= n;i++) {
		pos[col[i]].push_back(lef[i]);
		//cout << col[i] << "  " << lef[i] << endl;
		//cout << lef[i] << " " << rig[i] << endl;
	}
	for (int i = 1;i <= r;i++) {
		sort(pos[i].begin(), pos[i].end());
		/*
		cout << i << ": " << endl;
		for (int v:pos[i]) cout << v<< " ";
		cout << endl;
		*/
	}
	for (int i = 0;i < q;i++) {
		int r1, r2;
		cin >> r1 >> r2;
		if (cnt[r1] >= 300) cout << ans[cor[r1]][r2] << endl;
		else {
			int ans = 0;
			for (int v:node[r1]) {
				int rn = upper_bound(pos[r2].begin(), pos[r2].end(), rig[v] - 1) - pos[r2].begin();
				int ln = lower_bound(pos[r2].begin(), pos[r2].end(), lef[v]) - pos[r2].begin();
				ans += rn - ln;
			}
			cout << ans << endl;
		}
	}
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
 */

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 6 ms 6252 KB Output is correct
4 Correct 8 ms 6252 KB Output is correct
5 Correct 12 ms 6252 KB Output is correct
6 Correct 20 ms 6380 KB Output is correct
7 Correct 26 ms 6380 KB Output is correct
8 Correct 29 ms 6380 KB Output is correct
9 Correct 56 ms 6892 KB Output is correct
10 Correct 99 ms 6892 KB Output is correct
11 Correct 123 ms 7276 KB Output is correct
12 Correct 148 ms 7660 KB Output is correct
13 Correct 210 ms 7660 KB Output is correct
14 Correct 334 ms 8172 KB Output is correct
15 Correct 307 ms 11116 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2028 ms 11372 KB Output is correct
2 Correct 2476 ms 10988 KB Output is correct
3 Correct 3253 ms 13376 KB Output is correct
4 Correct 271 ms 8264 KB Output is correct
5 Correct 398 ms 9964 KB Output is correct
6 Correct 564 ms 11500 KB Output is correct
7 Correct 1143 ms 12908 KB Output is correct
8 Correct 1263 ms 20716 KB Output is correct
9 Correct 3033 ms 19832 KB Output is correct
10 Correct 3597 ms 32108 KB Output is correct
11 Correct 7201 ms 28524 KB Output is correct
12 Correct 1731 ms 17320 KB Output is correct
13 Correct 2248 ms 18412 KB Output is correct
14 Correct 2867 ms 20224 KB Output is correct
15 Correct 3867 ms 22796 KB Output is correct
16 Correct 3395 ms 29932 KB Output is correct
17 Correct 3366 ms 30104 KB Output is correct