oj.uz

Submission #99159

# Submission time Handle Problem Language Result Execution time Memory
99159 2019-03-01T04:01:21 Z shoemakerjo Regions (IOI09_regions) C++14
55 / 100
 2357 ms 35156 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) {
	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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6880 KB Output is correct
2 Correct 9 ms 6808 KB Output is correct
3 Correct 9 ms 6784 KB Output is correct
4 Correct 10 ms 6784 KB Output is correct
5 Correct 15 ms 6832 KB Output is correct
6 Correct 32 ms 6912 KB Output is correct
7 Correct 31 ms 6912 KB Output is correct
8 Correct 36 ms 6912 KB Output is correct
9 Correct 29 ms 7552 KB Output is correct
10 Correct 82 ms 7680 KB Output is correct
11 Correct 107 ms 8184 KB Output is correct
12 Correct 73 ms 8756 KB Output is correct
13 Correct 152 ms 8832 KB Output is correct
14 Correct 174 ms 9600 KB Output is correct
15 Correct 220 ms 12412 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 727 ms 13996 KB Output isn't correct
2 Incorrect 939 ms 13132 KB Output isn't correct
3 Incorrect 1351 ms 16420 KB Output isn't correct
4 Correct 243 ms 9512 KB Output is correct
5 Correct 185 ms 11252 KB Output is correct
6 Correct 674 ms 11264 KB Output is correct
7 Correct 887 ms 13184 KB Output is correct
8 Correct 792 ms 18612 KB Output is correct
9 Correct 1562 ms 21580 KB Output is correct
10 Correct 1990 ms 26216 KB Output is correct
11 Correct 2357 ms 22636 KB Output is correct
12 Incorrect 1016 ms 24108 KB Output isn't correct
13 Incorrect 1299 ms 24304 KB Output isn't correct
14 Incorrect 2020 ms 26852 KB Output isn't correct
15 Incorrect 1962 ms 29536 KB Output isn't correct
16 Incorrect 2106 ms 33928 KB Output isn't correct
17 Incorrect 2029 ms 35156 KB Output isn't correct