oj.uz

답안 #1065041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065041 2024-08-18T21:33:09 Z belgianbot Regions (IOI09_regions) C++17
1 / 100
 2951 ms 45832 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], 0)); 
				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], 0));
				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 2 ms 344 KB Output isn't correct
5 Incorrect 4 ms 344 KB Output isn't correct
6 Incorrect 9 ms 600 KB Output isn't correct
7 Incorrect 14 ms 600 KB Output isn't correct
8 Incorrect 15 ms 600 KB Output isn't correct
9 Incorrect 19 ms 1368 KB Output isn't correct
10 Incorrect 52 ms 1112 KB Output isn't correct
11 Incorrect 67 ms 1624 KB Output isn't correct
12 Incorrect 84 ms 2648 KB Output isn't correct
13 Incorrect 125 ms 2132 KB Output isn't correct
14 Incorrect 176 ms 3032 KB Output isn't correct
15 Incorrect 143 ms 8360 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1047 ms 8056 KB Output isn't correct
2 Incorrect 1351 ms 6244 KB Output isn't correct
3 Incorrect 1594 ms 11540 KB Output isn't correct
4 Incorrect 175 ms 3368 KB Output isn't correct
5 Incorrect 214 ms 6648 KB Output isn't correct
6 Incorrect 408 ms 8712 KB Output isn't correct
7 Incorrect 759 ms 11124 KB Output isn't correct
8 Incorrect 779 ms 24604 KB Output isn't correct
9 Incorrect 1609 ms 16300 KB Output isn't correct
10 Incorrect 1898 ms 45832 KB Output isn't correct
11 Incorrect 2951 ms 16900 KB Output isn't correct
12 Incorrect 992 ms 17624 KB Output isn't correct
13 Incorrect 1248 ms 18812 KB Output isn't correct
14 Incorrect 1595 ms 21516 KB Output isn't correct
15 Incorrect 2053 ms 26828 KB Output isn't correct
16 Incorrect 1600 ms 39612 KB Output isn't correct
17 Incorrect 1699 ms 40056 KB Output isn't correct