oj.uz

Submission #1064985

# Submission time Handle Problem Language Result Execution time Memory
1064985 2024-08-18T20:55:02 Z belgianbot Regions (IOI09_regions) C++17
23 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int cnt = 0, N, SQRT;

struct segTree {
	vector<map<int,int>> t;
	void build() {
		for (int i = N - 1; i > 0; i--) {
			for (auto x : t[i << 1]) t[i][x.first] += x.second;
			for (auto x : t[i << 1 | 1]) t[i][x.first] += x.second;
		}
	}
	int query(int l, int r, int c) {
		int res = 0;
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l&1){
				if (t[l].find(c) != t[l].end()) res += t[l][c];
				l++;
			}
			if (r&1) {
				r--;
				if (t[r].find(c) != t[r].end()) res += t[r][c];
			}
		}
		return res;
	}
};
segTree seg;
vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, map<int,int>> col;


map<int,int> dfs(int x) {
	seg.t[cnt + N][a[x]] = 1;
	in[x] = cnt++;
	
	map<int,int> curr;
	for (int y : child[x]) {
		map<int,int> mp = dfs(y);
		if (occ[a[x]] > SQRT) {
			if (mp.size() > curr.size()) swap(mp, curr);
			for (auto z : mp) curr[z.first] += z.second;
		}
	}
	for (auto z : curr) col[a[x]][z.first] += z.second;
	curr[a[x]]++;
	out[x] = cnt;
	return curr;
	
}

signed main() {
	ios::sync_with_stdio(false);
	int R, Q; cin >> N >> R >> Q;
	a.resize(N); child.resize(N); in.resize(N); out.resize(N); cin >> a[0]; a[0]--;
	occ.resize(R, 0); occ[a[0]]++;
	seg.t.resize(2 * N);
	for (int i = 1; i < N; i++) {
		int b; cin >> b >> a[i]; b--; a[i]--; occ[a[i]]++;
		child[b].push_back(i);
	}
	SQRT=sqrt(N);
	dfs(0);
	seg.build();
	vector<vector<int>> temp(R);
	for (int i = 0; i < N; i++) {
		if (occ[a[i]] <= SQRT) temp[a[i]].push_back(i);
	}
	
	while (Q--) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (occ[r1] > SQRT) cout << col[r1][r2] << '\n';
		
		else {
				int ans = 0;
			for (int x : temp[r1]) {
				ans += seg.query(in[x] + 1, out[x], r2);
			}
			cout << ans << '\n';
		}
	}
		
	return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 18 ms 1112 KB Output is correct
7 Correct 24 ms 1368 KB Output is correct
8 Correct 25 ms 1880 KB Output is correct
9 Correct 85 ms 5208 KB Output is correct
10 Correct 79 ms 8280 KB Output is correct
11 Correct 217 ms 11956 KB Output is correct
12 Correct 430 ms 17496 KB Output is correct
13 Correct 186 ms 18976 KB Output is correct
14 Incorrect 459 ms 22524 KB Output isn't correct
15 Incorrect 1994 ms 38684 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 7405 ms 51316 KB Output isn't correct
2 Incorrect 3513 ms 51296 KB Output isn't correct
3 Execution timed out 8076 ms 67920 KB Time limit exceeded
4 Correct 677 ms 27152 KB Output is correct
5 Correct 1371 ms 38648 KB Output is correct
6 Incorrect 548 ms 48436 KB Output isn't correct
7 Incorrect 2849 ms 70308 KB Output isn't correct
8 Incorrect 4815 ms 105772 KB Output isn't correct
9 Runtime error 181 ms 131072 KB Execution killed with signal 9
10 Runtime error 169 ms 131072 KB Execution killed with signal 9
11 Runtime error 162 ms 131072 KB Execution killed with signal 9
12 Runtime error 175 ms 131072 KB Execution killed with signal 9
13 Runtime error 162 ms 131072 KB Execution killed with signal 9
14 Runtime error 204 ms 131072 KB Execution killed with signal 9
15 Runtime error 158 ms 131072 KB Execution killed with signal 9
16 Runtime error 125 ms 131072 KB Execution killed with signal 9
17 Runtime error 138 ms 131072 KB Execution killed with signal 9