oj.uz

답안 #1064996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1064996 2024-08-18T21:14:25 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> curr;


void dfs(int x) {
	seg.t[cnt + N][a[x]] = 1;
	in[x] = cnt++;
	
	if (occ[a[x]] > SQRT) curr[a[x]]++;
	for (int y : child[x]) {
		dfs(y);
	}
	if (occ[a[x]] > SQRT) curr[a[x]] --;
	for (auto z : curr) col[z.first][a[x]] += z.second;
	out[x] = cnt;
	
}

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

# 결과 실행 시간 메모리 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 12 ms 1000 KB Output is correct
7 Correct 21 ms 1112 KB Output is correct
8 Correct 23 ms 1624 KB Output is correct
9 Correct 69 ms 3928 KB Output is correct
10 Correct 97 ms 6696 KB Output is correct
11 Correct 209 ms 9304 KB Output is correct
12 Correct 434 ms 13516 KB Output is correct
13 Correct 180 ms 14844 KB Output is correct
14 Correct 401 ms 17744 KB Output is correct
15 Correct 1811 ms 27860 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7054 ms 39752 KB Output is correct
2 Correct 3258 ms 40348 KB Output is correct
3 Execution timed out 8087 ms 51452 KB Time limit exceeded
4 Correct 613 ms 21172 KB Output is correct
5 Correct 1302 ms 28708 KB Output is correct
6 Correct 536 ms 38976 KB Output is correct
7 Correct 2724 ms 57540 KB Output is correct
8 Correct 4539 ms 83200 KB Output is correct
9 Execution timed out 8026 ms 113744 KB Time limit exceeded
10 Runtime error 383 ms 131072 KB Execution killed with signal 9
11 Runtime error 196 ms 131072 KB Execution killed with signal 9
12 Runtime error 236 ms 131072 KB Execution killed with signal 9
13 Runtime error 215 ms 131072 KB Execution killed with signal 9
14 Runtime error 256 ms 131072 KB Execution killed with signal 9
15 Runtime error 206 ms 131072 KB Execution killed with signal 9
16 Runtime error 170 ms 131072 KB Execution killed with signal 9
17 Runtime error 209 ms 131072 KB Execution killed with signal 9