Submission #854924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854924	2023-09-29T12:06:49 Z	rxlfd314	Regions (IOI09_regions)	C++17	100 / 100	3523 ms	127692 KB

regions

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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