Submission #99159

#	Time	Username	Problem	Language	Result	Execution time	Memory
99159		shoemakerjo	Regions (IOI09_regions)	C++14	55 / 100	2357 ms	35156 KiB

regions

#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) {
	int inc = 0;
	if (val[u] == cval) {
		inc++;
	}
	else {
		dpf[cspot][val[u]] += nseen;
	}

	for (int v : ch[u]) {
		dfsdown(v, nseen + inc);
	}
}

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());

		// cout << "   " << i << ": ";
		// for (int v : regsec[i]) cout << v << " ";
		// cout << endl;

		// cout << "     ";
		// for (pii vp : regfirst[i]) 
		// 	cout << "(" << vp.first << "," << vp.second << ") ";
		// cout << endl;

		if (mybc[i] == 0) continue;
		//do the root decomp things
		for (int j = 1; j <= N; j++) {
			curpref[j] = curpref[j-1];
			if (val[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 (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85