oj.uz

Submission #99160

# Submission time Handle Problem Language Result Execution time Memory
99160 2019-03-01T04:12:16 Z shoemakerjo Regions (IOI09_regions) C++14
100 / 100
 2235 ms 35160 KB 
#include <bits/stdc++.h>

using namespace std;

int N, R, Q;
#define pii pair<int, int>
using ll = long long;

//we can change the below things
const int blk = 1000;
const int numblk = 203;

const int maxn = 200010;
const int maxr = 25010;

vector<int> ch[maxn];

int dpf[numblk][maxr]; //dp if I am first
int dps[numblk][maxr]; //dp if I am second

int mybc[maxr];
int myct[maxr];

int par[maxn];
int val[maxn]; //which component i am in

vector<int> preorder;
int st[maxn];
int en[maxn];

vector<int> reg[maxr]; //regions 

vector<pii> regfirst[maxr];
vector<int> regsec[maxr];

void predfs(int u) {
	st[u] = preorder.size();
	preorder.push_back(u);
	for (int v : ch[u]) {
		predfs(v);
	}
	en[u] = preorder.size()-1;
}

int cval; //the current value
int cspot; //the mapped index (bc)

void dfsdown(int u, int nseen) {
	if (val[u] == cval) {
		nseen++;
	}
	dpf[cspot][val[u]] += nseen;
	
	for (int v : ch[u]) {
		dfsdown(v, nseen);
	}
}

int curpref[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> R >> Q;

	cin >> val[1];
	for (int i = 2; i <= N; i++) {
		cin >> par[i] >> val[i];
		ch[par[i]].push_back(i);
	}

	for (int i = 1; i <= N; i++) {
		myct[val[i]]++;
		reg[val[i]].push_back(i);
	}

	int numseen = 0;
	for (int i = 1; i <= R; i++) {
		if (myct[i] >= blk) {
			mybc[i] = ++numseen;
		}
	}

	preorder.push_back(-1);
	predfs(1);

	for (int i = 1; i <= N; i++) {
		regsec[val[i]].push_back(st[i]);
		regfirst[val[i]].push_back(pii(st[i], 1));
		regfirst[val[i]].push_back(pii(en[i]+1, -1));
	}

	for (int i = 1; i <= R; i++) {

		sort(regsec[i].begin(), regsec[i].end());
		sort(regfirst[i].begin(), regfirst[i].end());


		if (mybc[i] == 0) continue;
		//do the root decomp things
		for (int j = 1; j <= N; j++) {
			curpref[j] = curpref[j-1];
			if (val[preorder[j]] == i) {
				curpref[j]++;
			}
		}

		for (int j = 1; j <= N; j++) {
			dps[mybc[i]][val[j]] += 
				curpref[en[j]] - curpref[st[j]-1];
		}

		cval = i;
		cspot = mybc[i];

		dfsdown(1, 0);

	}

	int a, b;
	while (Q--) {
		cin >> a >> b;
		if (mybc[a]) {
			cout << dpf[mybc[a]][b] << endl;
		}
		else if (mybc[b]) {
			cout << dps[mybc[b]][a] << endl;
		}
		else {
			//actually do stuff (sliding window thing)

			int i1 = -1;
			int res = 0;
			int cv = 0;

			for (int v : regsec[b]) {
				while (i1 +1 < regfirst[a].size() && 
					regfirst[a][i1+1].first <= v) {

					// cout << "    -----this" << endl;
					cv += regfirst[a][i1+1].second;
					i1++;
				}
				res += cv;
			}

			cout << res << endl;

		}
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:137:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i1 +1 < regfirst[a].size() && 
            ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6784 KB Output is correct
2 Correct 7 ms 6784 KB Output is correct
3 Correct 9 ms 6784 KB Output is correct
4 Correct 8 ms 6912 KB Output is correct
5 Correct 11 ms 6832 KB Output is correct
6 Correct 13 ms 6912 KB Output is correct
7 Correct 34 ms 7040 KB Output is correct
8 Correct 35 ms 6912 KB Output is correct
9 Correct 55 ms 7460 KB Output is correct
10 Correct 82 ms 7692 KB Output is correct
11 Correct 73 ms 8024 KB Output is correct
12 Correct 117 ms 8832 KB Output is correct
13 Correct 99 ms 8852 KB Output is correct
14 Correct 170 ms 9604 KB Output is correct
15 Correct 209 ms 12400 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 14080 KB Output is correct
2 Correct 986 ms 13172 KB Output is correct
3 Correct 1466 ms 16540 KB Output is correct
4 Correct 231 ms 9464 KB Output is correct
5 Correct 317 ms 11252 KB Output is correct
6 Correct 651 ms 11252 KB Output is correct
7 Correct 855 ms 13088 KB Output is correct
8 Correct 727 ms 18548 KB Output is correct
9 Correct 1422 ms 21620 KB Output is correct
10 Correct 2007 ms 26224 KB Output is correct
11 Correct 2235 ms 22652 KB Output is correct
12 Correct 1076 ms 24168 KB Output is correct
13 Correct 1239 ms 24288 KB Output is correct
14 Correct 2031 ms 26880 KB Output is correct
15 Correct 1920 ms 29564 KB Output is correct
16 Correct 2123 ms 33820 KB Output is correct
17 Correct 2138 ms 35160 KB Output is correct