oj.uz

Submission #1064991

# Submission time Handle Problem Language Result Execution time Memory
1064991 2024-08-18T21:08:36 Z belgianbot Regions (IOI09_regions) C++17
50 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt = 0, N, SQRT, R;

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;
		}
	}
	ll query(int l, int r, int c) {
		ll res = 0;
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l&1){
				if (t[l].count(c)) res += t[l][c];
				l++;
			}
			if (r&1) {
				r--;
				if (t[r].count(c)) res += t[r][c];
			}
		}
		return res;
	}
};
segTree seg;
vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, vector<ll>> 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 (mp.size() > curr.size()) swap(mp, curr);
		for (auto z : mp) curr[z.first] += z.second;
	}
	if (occ[a[x]] > SQRT) 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 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);
	vector<vector<int>> temp(R);
	for (int i = 0; i < N; i++) {
		if (occ[a[i]] <= SQRT) temp[a[i]].push_back(i);

	}
	for (int i = 0; i < R; i++) {
		if (occ[i] > SQRT) col[i].resize(R);
	}
	dfs(0);
	seg.build();
	
	
	while (Q--) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (occ[r1] > SQRT) cout << col[r1][r2] << '\n';
		
		else {
			ll ans = 0;
			for (int x : temp[r1]) {
				ans += seg.query(in[x] + 1, out[x], r2);
			}
			cout << ans << '\n';
		}
	}
		
	return 0;
}

Subtask #1
15.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 3 ms 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 14 ms 1048 KB Output is correct
7 Correct 23 ms 1112 KB Output is correct
8 Correct 24 ms 1624 KB Output is correct
9 Correct 77 ms 4184 KB Output is correct
10 Correct 76 ms 6744 KB Output is correct
11 Correct 208 ms 9512 KB Output is correct
12 Correct 430 ms 13932 KB Output is correct
13 Correct 162 ms 14840 KB Output is correct
14 Correct 451 ms 17640 KB Output is correct
15 Correct 1854 ms 31608 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6980 ms 41156 KB Output is correct
2 Correct 3365 ms 40536 KB Output is correct
3 Execution timed out 8013 ms 54864 KB Time limit exceeded
4 Correct 640 ms 21320 KB Output is correct
5 Correct 1339 ms 31072 KB Output is correct
6 Correct 792 ms 39488 KB Output is correct
7 Correct 2938 ms 57992 KB Output is correct
8 Correct 7091 ms 89592 KB Output is correct
9 Execution timed out 8051 ms 115536 KB Time limit exceeded
10 Runtime error 5465 ms 131072 KB Execution killed with signal 9
11 Runtime error 283 ms 131072 KB Execution killed with signal 9
12 Runtime error 400 ms 131072 KB Execution killed with signal 9
13 Runtime error 873 ms 131072 KB Execution killed with signal 9
14 Runtime error 1040 ms 131072 KB Execution killed with signal 9
15 Runtime error 4447 ms 131072 KB Execution killed with signal 9
16 Execution timed out 8064 ms 80840 KB Time limit exceeded
17 Execution timed out 8010 ms 78204 KB Time limit exceeded