oj.uz

Submission #1064984

# Submission time Handle Problem Language Result Execution time Memory
1064984 2024-08-18T20:51:59 Z belgianbot Regions (IOI09_regions) C++17
13 / 100
 1316 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) res += t[l++][c];
			if (r&1) 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 2 ms 492 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 7 ms 1332 KB Output is correct
6 Correct 15 ms 2124 KB Output is correct
7 Correct 29 ms 4948 KB Output is correct
8 Correct 46 ms 7004 KB Output is correct
9 Correct 153 ms 18256 KB Output is correct
10 Correct 218 ms 34584 KB Output is correct
11 Correct 860 ms 81256 KB Output is correct
12 Correct 1316 ms 101740 KB Output is correct
13 Correct 520 ms 81152 KB Output is correct
14 Runtime error 1012 ms 131072 KB Execution killed with signal 9
15 Runtime error 1052 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 982 ms 131072 KB Execution killed with signal 9
2 Runtime error 817 ms 131072 KB Execution killed with signal 9
3 Runtime error 717 ms 131072 KB Execution killed with signal 9
4 Runtime error 892 ms 131072 KB Execution killed with signal 9
5 Runtime error 1088 ms 131072 KB Execution killed with signal 9
6 Incorrect 714 ms 75660 KB Output isn't correct
7 Runtime error 883 ms 131072 KB Execution killed with signal 9
8 Runtime error 382 ms 131072 KB Execution killed with signal 9
9 Runtime error 166 ms 131072 KB Execution killed with signal 9
10 Runtime error 174 ms 131072 KB Execution killed with signal 9
11 Runtime error 164 ms 131072 KB Execution killed with signal 9
12 Runtime error 184 ms 131072 KB Execution killed with signal 9
13 Runtime error 166 ms 131072 KB Execution killed with signal 9
14 Runtime error 180 ms 131072 KB Execution killed with signal 9
15 Runtime error 160 ms 131072 KB Execution killed with signal 9
16 Runtime error 150 ms 131072 KB Execution killed with signal 9
17 Runtime error 158 ms 131072 KB Execution killed with signal 9