Submission #722851

#	Time	Username	Problem	Language	Result	Execution time	Memory
722851		horiseun	Regions (IOI09_regions)	C++11	100 / 100	4035 ms	42556 KiB

regions

#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int SQRT = 510;
 
int n, r, q, idx;
vector<int> adj[200005], blocks[25005], dfsorder, pref;
int in[200005], out[200005], region[200005];
unordered_map<int, int> ans[25005];

void dfs(int curr, int par) {
    in[curr] = ++idx;
    blocks[region[curr]].push_back(idx);
    dfsorder.push_back(curr);
    for (auto i : adj[curr]) {
        if (i == par) continue;
        dfs(i, curr);
    }
    out[curr] = idx;
};

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);

	cin >> n >> r >> q >> region[1];
	for (int i = 2, x; i <= n; ++i) {
		cin >> x >> region[i];
		adj[x].push_back(i);
		adj[i].push_back(x);
	}

	idx = -1;
	dfs(1, -1);
	pref.resize(idx + 5, 0);
	for (int i = 1; i <= r; ++i) {
		if (blocks[i].size() >= SQRT) {
			for (int j : blocks[i]) {
				pref[j]++;
				pref[out[dfsorder[j]] + 1]--;
			}
			for (int j = 1; j <= idx; ++j) {
				pref[j] += pref[j - 1];
				ans[i][region[dfsorder[j]]] += pref[j];
			}
			for (int j = 0; j < idx + 5; j++) pref[j] = 0;
		}
    }

	for (int i = 0, r1, r2, ret; i < q; i++) {
		cin >> r1 >> r2;
		if (blocks[r1].size() >= SQRT) {
			cout << ans[r1][r2] << "\n" << flush;
		} else {
			ret = 0;
			for (int j : blocks[r1]) {
				ret += upper_bound(blocks[r2].begin(), blocks[r2].end(), out[dfsorder[j]]) - lower_bound(blocks[r2].begin(), blocks[r2].end(), j);
			}
			cout << ret << "\n" << flush;
		}
	}
}

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