oj.uz

Submission #652552

# Submission time Handle Problem Language Result Execution time Memory
652552 2022-10-23T04:52:38 Z rxlfd314 Regions (IOI09_regions) C++17
0 / 100
 489 ms 29032 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define cerr if (false) cout
constexpr int mxN = 2e5, mxR = 25e3;
int N, R, Q, rgn[mxN];
vector<int> adj[mxN], rgnLst[mxR];
int tin[mxN], tout[mxN], timer;
void getTimes(int f) {
	tin[f] = timer++;
	for (int nf : adj[f]) {
		getTimes(nf);
	}
	tout[f] = timer - 1;
}
int acnt[mxN];
void getacnt(int f, int t, int cur = 0) {
	acnt[f] = cur;
	cur += rgn[f] == t;
	for (int nf : adj[f]) {
		getacnt(nf, t, cur);
	}
}
bool comp(int a, int b) {
	return tin[a] < tin[b];
}
signed main() {
#ifdef cerr
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
#endif
	cin >> N >> R >> Q >> rgn[0];
	rgnLst[--rgn[0]].push_back(0);
	for (int i = 1, a; i < N; i++) {
		cin >> a >> rgn[i];
		adj[--a].push_back(i);
		rgnLst[--rgn[i]].push_back(i);
	}
	getTimes(0);
	vector<int> big;
	constexpr int BSZ = 447;
	for (int i = 0; i < R; i++) {
		if (rgnLst[i].size() > BSZ) {
			big.push_back(i);
		}
		sort(rgnLst[i].begin(), rgnLst[i].end(), comp);
	}
	int ans[big.size()][R][2], psum[N];
	memset(ans, 0, sizeof(ans));
	for (int i = 0; i < big.size(); i++) { // O(sqrt(N) * (4 * N + R))
		getacnt(0, big[i]);
		memset(psum, 0, sizeof(psum));
		for (int j : rgnLst[big[i]]) {
			psum[tin[j]]++;
		}
		for (int j = 1; j < N; j++) {
			psum[j] += psum[j-1];
		}
		for (int j = 0; j < R; j++) {
			if (j == big[i]) continue;
			for (int k : rgnLst[j]) {
				ans[i][j][0] += acnt[k];
				ans[i][j][1] += psum[tout[k]] - (tin[k] > 0 ? psum[tin[k]-1] : 0);
			}
		}
	}
	for (int q = 0, a, b; q < Q; q++) { // O(N * sqrt(N) * log_2(sqrt(N)))
		cin >> a >> b;
		a--, b--;
		if (rgnLst[a].size() > BSZ) {
			cout << ans[lower_bound(big.begin(),big.end(),a)-big.begin()][b][0] << '\n';
		} else if (rgnLst[b].size() > BSZ) {
			cout << ans[lower_bound(big.begin(),big.end(),b)-big.begin()][a][1] << '\n';
		} else {
			ll res = 0;
			for (int i : rgnLst[a]) {
				res += upper_bound(rgnLst[b].begin(), rgnLst[b].end(), tout[i], comp) - lower_bound(rgnLst[b].begin(), rgnLst[b].end(), tin[i], comp); 
			}
			cout << res << '\n';
		}
	}
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < big.size(); i++) { // O(sqrt(N) * (4 * N + R))
      |                  ~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 5584 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 5584 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 5712 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 5968 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6096 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 6352 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 6736 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 6480 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 6992 KB Time limit exceeded (wall clock)
15 Execution timed out 16 ms 8784 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 59 ms 9928 KB Time limit exceeded (wall clock)
2 Execution timed out 66 ms 9188 KB Time limit exceeded (wall clock)
3 Execution timed out 47 ms 11392 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 6992 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 8144 KB Time limit exceeded (wall clock)
6 Execution timed out 116 ms 11640 KB Time limit exceeded (wall clock)
7 Execution timed out 66 ms 10568 KB Time limit exceeded (wall clock)
8 Execution timed out 314 ms 20680 KB Time limit exceeded (wall clock)
9 Execution timed out 55 ms 13512 KB Time limit exceeded (wall clock)
10 Execution timed out 380 ms 29032 KB Time limit exceeded (wall clock)
11 Execution timed out 75 ms 13768 KB Time limit exceeded (wall clock)
12 Execution timed out 127 ms 16664 KB Time limit exceeded (wall clock)
13 Execution timed out 110 ms 16584 KB Time limit exceeded (wall clock)
14 Execution timed out 489 ms 19656 KB Time limit exceeded (wall clock)
15 Execution timed out 109 ms 19160 KB Time limit exceeded (wall clock)
16 Execution timed out 87 ms 22420 KB Time limit exceeded (wall clock)
17 Execution timed out 225 ms 24452 KB Time limit exceeded (wall clock)