oj.uz

답안 #854916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854916 2023-09-29T12:02:04 Z rxlfd314 Regions (IOI09_regions) C++17
0 / 100
 137 ms 127900 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);
	}
}

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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 9048 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 11352 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 11352 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 11352 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 11352 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 13912 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 15904 KB Time limit exceeded (wall clock)
11 Execution timed out 9 ms 18520 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 20860 KB Time limit exceeded (wall clock)
13 Execution timed out 14 ms 22360 KB Time limit exceeded (wall clock)
14 Execution timed out 19 ms 26948 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 34128 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 39 ms 50392 KB Time limit exceeded (wall clock)
2 Execution timed out 44 ms 50928 KB Time limit exceeded (wall clock)
3 Execution timed out 45 ms 60504 KB Time limit exceeded (wall clock)
4 Execution timed out 20 ms 27168 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 31176 KB Time limit exceeded (wall clock)
6 Execution timed out 30 ms 38644 KB Time limit exceeded (wall clock)
7 Execution timed out 44 ms 47764 KB Time limit exceeded (wall clock)
8 Execution timed out 56 ms 67864 KB Time limit exceeded (wall clock)
9 Execution timed out 106 ms 91676 KB Time limit exceeded (wall clock)
10 Execution timed out 106 ms 107956 KB Time limit exceeded (wall clock)
11 Execution timed out 123 ms 113480 KB Time limit exceeded (wall clock)
12 Execution timed out 136 ms 112976 KB Time limit exceeded (wall clock)
13 Execution timed out 107 ms 113584 KB Time limit exceeded (wall clock)
14 Execution timed out 137 ms 114932 KB Time limit exceeded (wall clock)
15 Execution timed out 109 ms 120440 KB Time limit exceeded (wall clock)
16 Execution timed out 99 ms 127900 KB Time limit exceeded (wall clock)
17 Execution timed out 104 ms 126072 KB Time limit exceeded (wall clock)