oj.uz

답안 #378839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378839 2021-03-17T05:57:00 Z 8e7 Regions (IOI09_regions) C++14
13 / 100
 207 ms 15084 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;
const int siz = 128;
vector<int> adj[maxn], pos[maxc], node[maxc];
int col[maxc], cnt[maxc], ind[1000], cor[maxc];

int ans[505][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] >= 500) {
			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] >= 500) 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();
				//cout << v << ' ' << " " << rn << " " << ln << endl;
				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
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 7 ms 6252 KB Output is correct
4 Correct 7 ms 6252 KB Output is correct
5 Correct 13 ms 6252 KB Output is correct
6 Correct 19 ms 6380 KB Output is correct
7 Correct 25 ms 6380 KB Output is correct
8 Correct 23 ms 6380 KB Output is correct
9 Correct 63 ms 7020 KB Output is correct
10 Correct 103 ms 6892 KB Output is correct
11 Correct 154 ms 7276 KB Output is correct
12 Correct 148 ms 7660 KB Output is correct
13 Correct 207 ms 7660 KB Output is correct
14 Runtime error 23 ms 14572 KB Execution killed with signal 11
15 Runtime error 24 ms 14444 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 14572 KB Execution killed with signal 11
2 Runtime error 23 ms 14572 KB Execution killed with signal 11
3 Runtime error 24 ms 14572 KB Execution killed with signal 11
4 Runtime error 31 ms 14700 KB Execution killed with signal 11
5 Runtime error 25 ms 14700 KB Execution killed with signal 11
6 Runtime error 25 ms 14828 KB Execution killed with signal 11
7 Runtime error 27 ms 14956 KB Execution killed with signal 11
8 Runtime error 27 ms 14780 KB Execution killed with signal 11
9 Runtime error 25 ms 14828 KB Execution killed with signal 11
10 Runtime error 26 ms 15080 KB Execution killed with signal 11
11 Runtime error 25 ms 15084 KB Execution killed with signal 11
12 Runtime error 25 ms 14956 KB Execution killed with signal 11
13 Runtime error 29 ms 15084 KB Execution killed with signal 11
14 Runtime error 25 ms 14956 KB Execution killed with signal 11
15 Runtime error 27 ms 15084 KB Execution killed with signal 11
16 Runtime error 25 ms 14956 KB Execution killed with signal 11
17 Runtime error 24 ms 14956 KB Execution killed with signal 11