oj.uz

답안 #854924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854924 2023-09-29T12:06:49 Z rxlfd314 Regions (IOI09_regions) C++17
100 / 100
 3523 ms 127692 KB 
#include <bits/stdc++.h>
using namespace std;
 
constexpr int mxN = 200069, BSZ = 125; // wtf 125 works??? this is so cringe
int N, R, Q, H[mxN], rgnOrd[mxN>>3], revOrd[mxN>>3];
vector<int> adj[mxN], rgnLst[mxN>>3], rgnLst2[mxN>>3];
 
int timer, tin[mxN], tout[mxN];
int tdall[BSZ][BSZ], td[mxN][BSZ];
void dfs(int f) {
	tin[f] = timer++;
	for (int i = 0; i < min(R, BSZ) && revOrd[H[f]] < BSZ; i++) {
		tdall[revOrd[H[f]]][i] += td[f][i];
	}
	for (int nf : adj[f]) {
		for (int i = 0; i < min(R, BSZ); i++) {
			td[nf][i] = td[f][i] + (rgnOrd[i] == H[f]);
		}
		dfs(nf);
	}
	tout[f] = timer-1;
}
 
signed main() {
	scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
	rgnLst[--H[0]].push_back(0);
	for (int i = 1, p; i < N; i++) {
		scanf("%d%d", &p, &H[i]);
		adj[--p].push_back(i);
		rgnLst[--H[i]].push_back(i);
	}
 
	iota(rgnOrd, rgnOrd+R, 0);
	sort(rgnOrd, rgnOrd+R, [&](const int &a, const int &b) {
		return rgnLst[a].size() > rgnLst[b].size();					 
	});
	for (int i = 0; i < R; i++) {
		revOrd[rgnOrd[i]] = i;
	}
	dfs(0);
	for (int i = 0; i < R; i++) {
		for (int j : rgnLst[i]) {
			rgnLst2[i].push_back(tin[j]);
		}
		sort(rgnLst2[i].begin(), rgnLst2[i].end());
	}
 
	for (int a, b, ans; Q--; ) {
		scanf("%d%d", &a, &b);
		a--, b--;
		ans = 0;
		if (revOrd[a] < BSZ && revOrd[b] < BSZ) {
			ans = tdall[revOrd[b]][revOrd[a]];
		} else if (revOrd[a] < BSZ) {
			for (int i : rgnLst[b]) {
				ans += td[i][revOrd[a]];
			}
		} else {
			for (int i : rgnLst[a]) {
				ans += upper_bound(rgnLst2[b].begin(), rgnLst2[b].end(), tout[i]) - lower_bound(rgnLst2[b].begin(), rgnLst2[b].end(), tin[i]);
			}
		}
		printf("%d\n", ans);
      	fflush(stdout);
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d%d%d", &N, &R, &Q, &H[0]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d%d", &p, &H[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 3 ms 9048 KB Output is correct
5 Correct 6 ms 11352 KB Output is correct
6 Correct 11 ms 11604 KB Output is correct
7 Correct 13 ms 11352 KB Output is correct
8 Correct 18 ms 11352 KB Output is correct
9 Correct 28 ms 13912 KB Output is correct
10 Correct 45 ms 15960 KB Output is correct
11 Correct 77 ms 18264 KB Output is correct
12 Correct 81 ms 20792 KB Output is correct
13 Correct 110 ms 22360 KB Output is correct
14 Correct 136 ms 27084 KB Output is correct
15 Correct 164 ms 34232 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 741 ms 50548 KB Output is correct
2 Correct 745 ms 51144 KB Output is correct
3 Correct 1529 ms 60652 KB Output is correct
4 Correct 144 ms 27092 KB Output is correct
5 Correct 199 ms 31112 KB Output is correct
6 Correct 326 ms 38568 KB Output is correct
7 Correct 494 ms 47656 KB Output is correct
8 Correct 644 ms 67760 KB Output is correct
9 Correct 1318 ms 91668 KB Output is correct
10 Correct 2083 ms 108112 KB Output is correct
11 Correct 3523 ms 113508 KB Output is correct
12 Correct 1012 ms 112956 KB Output is correct
13 Correct 1335 ms 113584 KB Output is correct
14 Correct 1481 ms 115132 KB Output is correct
15 Correct 2134 ms 120460 KB Output is correct
16 Correct 1911 ms 127692 KB Output is correct
17 Correct 1936 ms 125980 KB Output is correct