Submission #378839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378839	2021-03-17T05:57:00 Z	8e7	Regions (IOI09_regions)	C++14	13 / 100	207 ms	15084 KB

regions

//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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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