oj.uz

답안 #1065052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065052 2024-08-18T21:48:02 Z belgianbot Regions (IOI09_regions) C++17
1 / 100
 2925 ms 45828 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt = 0, N, SQRT, R;

vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, vector<ll>> col;
map<int,int> curr;
vector<vector<pair<int,int>>> pref;

void dfs(int x) {
	int last = 0;
	if (!pref[a[x]].empty()) last = pref[a[x]].back().second;
	pref[a[x]].push_back({cnt, last + 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]]++; pref.resize(R);
	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);
	
	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]) {
				auto it = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(out[x], -1)); 
				if (it == pref[r2].begin()) continue;
				it--;
				if ((*it).second < in[x]) continue;
				int last = 0;
				auto it2 = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(in[x], -1));
				if (it2 != pref[r2].begin()) {
					it2--;
					last = (*it2).second;
				}
				ans += (*it).second - last;
			}
			cout << ans << '\n';
		}
	}
		
	return 0;
}

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Incorrect 3 ms 344 KB Output isn't correct
5 Incorrect 4 ms 344 KB Output isn't correct
6 Incorrect 13 ms 600 KB Output isn't correct
7 Incorrect 17 ms 344 KB Output isn't correct
8 Incorrect 13 ms 600 KB Output isn't correct
9 Incorrect 25 ms 1368 KB Output isn't correct
10 Incorrect 46 ms 1112 KB Output isn't correct
11 Incorrect 77 ms 1624 KB Output isn't correct
12 Incorrect 88 ms 2648 KB Output isn't correct
13 Incorrect 122 ms 2136 KB Output isn't correct
14 Incorrect 194 ms 3036 KB Output isn't correct
15 Incorrect 130 ms 8280 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1097 ms 8060 KB Output isn't correct
2 Incorrect 1314 ms 6232 KB Output isn't correct
3 Incorrect 1610 ms 11544 KB Output isn't correct
4 Incorrect 189 ms 3408 KB Output isn't correct
5 Incorrect 258 ms 6644 KB Output isn't correct
6 Incorrect 388 ms 8708 KB Output isn't correct
7 Incorrect 784 ms 11112 KB Output isn't correct
8 Incorrect 777 ms 24608 KB Output isn't correct
9 Incorrect 1601 ms 16300 KB Output isn't correct
10 Incorrect 1824 ms 45828 KB Output isn't correct
11 Incorrect 2925 ms 16896 KB Output isn't correct
12 Incorrect 943 ms 17632 KB Output isn't correct
13 Incorrect 1272 ms 18808 KB Output isn't correct
14 Incorrect 1513 ms 21520 KB Output isn't correct
15 Incorrect 2009 ms 26960 KB Output isn't correct
16 Incorrect 1615 ms 39616 KB Output isn't correct
17 Incorrect 1719 ms 40056 KB Output isn't correct