oj.uz

Submission #722851

# Submission time Handle Problem Language Result Execution time Memory
722851 2023-04-13T02:35:46 Z horiseun Regions (IOI09_regions) C++11
100 / 100
 4035 ms 42556 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6864 KB Output is correct
2 Correct 5 ms 6864 KB Output is correct
3 Correct 6 ms 6992 KB Output is correct
4 Correct 8 ms 6992 KB Output is correct
5 Correct 12 ms 6992 KB Output is correct
6 Correct 12 ms 6992 KB Output is correct
7 Correct 36 ms 6992 KB Output is correct
8 Correct 43 ms 7120 KB Output is correct
9 Correct 47 ms 7520 KB Output is correct
10 Correct 88 ms 7624 KB Output is correct
11 Correct 116 ms 7888 KB Output is correct
12 Correct 165 ms 8400 KB Output is correct
13 Correct 181 ms 8400 KB Output is correct
14 Correct 278 ms 8784 KB Output is correct
15 Correct 291 ms 11204 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1914 ms 11968 KB Output is correct
2 Correct 2212 ms 11752 KB Output is correct
3 Correct 2866 ms 13760 KB Output is correct
4 Correct 236 ms 8872 KB Output is correct
5 Correct 385 ms 10324 KB Output is correct
6 Correct 1251 ms 10316 KB Output is correct
7 Correct 1754 ms 11328 KB Output is correct
8 Correct 1365 ms 16004 KB Output is correct
9 Correct 2481 ms 16752 KB Output is correct
10 Correct 4035 ms 21264 KB Output is correct
11 Correct 3978 ms 19132 KB Output is correct
12 Correct 1484 ms 19208 KB Output is correct
13 Correct 2121 ms 19872 KB Output is correct
14 Correct 2313 ms 34252 KB Output is correct
15 Correct 3545 ms 24148 KB Output is correct
16 Correct 3289 ms 29748 KB Output is correct
17 Correct 2808 ms 42556 KB Output is correct