oj.uz

Submission #586920

# Submission time Handle Problem Language Result Execution time Memory
586920 2022-07-01T04:08:13 Z pavement Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 118976 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, cent, tot_sz, sz[240005], A[240005], B[240005], inc[240005], down[240005], dep[240005], par[240005], anc[25][240005], wei[25][240005];
bool vis[240005];
char C[240005];
vector<ii> adj[240005], vec[240005];

int get_sizes(int n, int e = -1) {
	sz[n] = 1;
	for (auto [u, w] : adj[n]) if (u != e && !vis[u])
		sz[n] += get_sizes(u, n);
	return sz[n];
}

void get_centroid(int n, int e = -1) {
	int m = tot_sz - sz[n];
	for (auto [u, w] : adj[n]) if (u != e && !vis[u]) {
		get_centroid(u, n);
		m = max(m, sz[u]);
	}
	if (m <= tot_sz / 2) cent = n;
}

void dfs(int n, int e = -1, int prv = -1) {
	anc[0][n] = e;
	wei[0][n] = prv;
	for (int k = 1; k < 20; k++)
		if (anc[k - 1][n] != -1) {
			anc[k][n] = anc[k - 1][anc[k - 1][n]];
			wei[k][n] = max(wei[k - 1][n], wei[k - 1][anc[k - 1][n]]);
		}
	for (auto [u, w] : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		if (w < prv) inc[u] = inc[n], down[u] = n;
		else down[u] = down[n], inc[u] = n;
		dfs(u, n, w);
	}
}

bool qry(int u, int v, int t) {
	int ou = u, ov = v, m_w = 0;
	bool has_swap = 0;
	if (dep[u] > dep[v]) {
		swap(u, v);
		has_swap = 1;
	}
	for (int k = 19; k >= 0; k--)
		if (dep[v] - (1 << k) >= dep[u]) {
			m_w = max(m_w, wei[k][v]);
			v = anc[k][v];
		}
	if (u == v) {
		if (m_w > t) return 0;
		if (dep[ou] <= dep[ov]) return dep[down[ov]] <= dep[ou];
		else return dep[inc[ou]] <= dep[ov];
	}
	if (has_swap) swap(u, v);
	for (int k = 19; k >= 0; k--)
		if (anc[k][u] != anc[k][v]) {
			m_w = max({m_w, wei[k][u], wei[k][v]});
			u = anc[k][u];
			v = anc[k][v];
		}
	int lca = anc[0][u];
	m_w = max({m_w, wei[0][u], wei[0][v]});
	return m_w < t && dep[inc[ou]] <= dep[lca] && dep[down[ov]] <= dep[lca] && wei[0][u] < wei[0][v];
}

ii get_ends(int u, int v) {
	int ou = u, ov = v;
	bool has_swap = 0;
	assert(u != v);
	if (dep[u] > dep[v]) {
		swap(u, v);
		has_swap = 1;
	}
	for (int k = 19; k >= 0; k--)
		if (dep[v] - (1 << k) >= dep[u] + 1) v = anc[k][v];
	if (u == anc[0][v]) {
		auto ret = mp(wei[0][v], wei[0][has_swap ? ou : ov]);
		if (has_swap) swap(ret.first, ret.second);
		return ret;
	}
	auto ret = mp(wei[0][ou], wei[0][ov]);
	return ret;
}

void decomp(int n, int e = -1) {
	get_sizes(n);
	tot_sz = sz[n];
	cent = -1;
	get_centroid(n);
	assert(cent != -1);
	vis[cent] = 1;
	par[cent] = e;
	int orig_cent = cent;
	for (auto [u, w] : adj[cent]) if (!vis[u])
		decomp(u, orig_cent);
}

main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N + K - 1; i++) {
		cin >> C[i];
		if (C[i] == 'S' || C[i] == 'Q') cin >> A[i] >> B[i];
		else cin >> A[i];
		if (C[i] == 'S') {
			adj[A[i]].eb(B[i], i);
			adj[B[i]].eb(A[i], i);
		}
	}
	inc[1] = down[1] = 1;
	dfs(1);
	decomp(1);
	for (int i = 1; i <= N; i++) {
		for (int u = par[i]; u != -1; u = par[u]) {
			if (qry(u, i, (int)1e9)) {
				auto curr = get_ends(u, i);
				vec[u].eb(curr.first, curr.second);
			}
		}
	}
	for (int i = 1; i <= N + K - 1; i++) {
		if (C[i] == 'Q') {
			if (qry(B[i], A[i], i)) cout << "yes\n";
			else cout << "no\n";
		} else if (C[i] == 'C') {
			int ans = 1;
			for (auto [x, y] : vec[A[i]])
				if (y < i) ans++;
			for (int u = par[A[i]]; u != -1; u = par[u]) {
				if (qry(A[i], u, i)) {
					auto curr = get_ends(A[i], u);
					ans++;
					for (auto [x, y] : vec[u])
						if (curr.second < x && y < i) ans++;
				}
			}
			cout << ans << '\n';
		}
	}
}

Compilation message

servers.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main() {
      | ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61892 KB Output is correct
2 Correct 68 ms 63156 KB Output is correct
3 Correct 79 ms 63188 KB Output is correct
4 Correct 79 ms 63412 KB Output is correct
5 Correct 69 ms 63676 KB Output is correct
6 Correct 57 ms 62992 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61892 KB Output is correct
2 Correct 68 ms 63156 KB Output is correct
3 Correct 79 ms 63188 KB Output is correct
4 Correct 79 ms 63412 KB Output is correct
5 Correct 69 ms 63676 KB Output is correct
6 Correct 57 ms 62992 KB Output is correct
7 Correct 58 ms 61840 KB Output is correct
8 Correct 94 ms 62800 KB Output is correct
9 Correct 142 ms 62852 KB Output is correct
10 Correct 135 ms 63120 KB Output is correct
11 Correct 137 ms 63352 KB Output is correct
12 Correct 279 ms 62776 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 61832 KB Output is correct
2 Correct 219 ms 80836 KB Output is correct
3 Correct 236 ms 80784 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 61832 KB Output is correct
2 Correct 219 ms 80836 KB Output is correct
3 Correct 236 ms 80784 KB Output is correct
4 Correct 51 ms 61788 KB Output is correct
5 Execution timed out 3549 ms 80808 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61920 KB Output is correct
2 Correct 457 ms 106388 KB Output is correct
3 Correct 499 ms 106336 KB Output is correct
4 Correct 497 ms 118836 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 61920 KB Output is correct
2 Correct 457 ms 106388 KB Output is correct
3 Correct 499 ms 106336 KB Output is correct
4 Correct 497 ms 118836 KB Output is correct
5 Correct 57 ms 61900 KB Output is correct
6 Correct 740 ms 105980 KB Output is correct
7 Correct 2117 ms 118012 KB Output is correct
8 Correct 983 ms 105572 KB Output is correct
9 Correct 957 ms 105660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 61820 KB Output is correct
2 Correct 340 ms 97208 KB Output is correct
3 Correct 358 ms 87884 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 61820 KB Output is correct
2 Correct 340 ms 97208 KB Output is correct
3 Correct 358 ms 87884 KB Output is correct
4 Correct 65 ms 61772 KB Output is correct
5 Correct 1576 ms 97120 KB Output is correct
6 Correct 441 ms 87372 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 61900 KB Output is correct
2 Correct 427 ms 106536 KB Output is correct
3 Correct 472 ms 106436 KB Output is correct
4 Correct 459 ms 118848 KB Output is correct
5 Correct 53 ms 61772 KB Output is correct
6 Correct 364 ms 97228 KB Output is correct
7 Correct 326 ms 87956 KB Output is correct
8 Correct 730 ms 93608 KB Output is correct
9 Correct 698 ms 92684 KB Output is correct
10 Correct 1271 ms 107680 KB Output is correct
11 Correct 1387 ms 106996 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 61900 KB Output is correct
2 Correct 427 ms 106536 KB Output is correct
3 Correct 472 ms 106436 KB Output is correct
4 Correct 459 ms 118848 KB Output is correct
5 Correct 53 ms 61772 KB Output is correct
6 Correct 364 ms 97228 KB Output is correct
7 Correct 326 ms 87956 KB Output is correct
8 Correct 730 ms 93608 KB Output is correct
9 Correct 698 ms 92684 KB Output is correct
10 Correct 1271 ms 107680 KB Output is correct
11 Correct 1387 ms 106996 KB Output is correct
12 Correct 56 ms 61932 KB Output is correct
13 Correct 746 ms 105948 KB Output is correct
14 Correct 2093 ms 117924 KB Output is correct
15 Correct 958 ms 105524 KB Output is correct
16 Correct 934 ms 105476 KB Output is correct
17 Correct 51 ms 61836 KB Output is correct
18 Correct 1514 ms 96904 KB Output is correct
19 Correct 414 ms 87444 KB Output is correct
20 Correct 811 ms 92084 KB Output is correct
21 Correct 842 ms 92448 KB Output is correct
22 Correct 2587 ms 106224 KB Output is correct
23 Execution timed out 3558 ms 114016 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 61900 KB Output is correct
2 Correct 73 ms 63096 KB Output is correct
3 Correct 65 ms 63164 KB Output is correct
4 Correct 80 ms 63408 KB Output is correct
5 Correct 72 ms 63696 KB Output is correct
6 Correct 64 ms 62928 KB Output is correct
7 Correct 52 ms 61900 KB Output is correct
8 Correct 221 ms 80780 KB Output is correct
9 Correct 248 ms 80828 KB Output is correct
10 Correct 53 ms 61884 KB Output is correct
11 Correct 444 ms 106512 KB Output is correct
12 Correct 458 ms 106356 KB Output is correct
13 Correct 474 ms 118976 KB Output is correct
14 Correct 51 ms 61868 KB Output is correct
15 Correct 335 ms 97284 KB Output is correct
16 Correct 327 ms 87884 KB Output is correct
17 Correct 612 ms 93568 KB Output is correct
18 Correct 571 ms 92444 KB Output is correct
19 Correct 1183 ms 107628 KB Output is correct
20 Correct 1362 ms 106912 KB Output is correct
21 Correct 226 ms 82240 KB Output is correct
22 Correct 250 ms 82748 KB Output is correct
23 Correct 292 ms 88748 KB Output is correct
24 Correct 298 ms 89932 KB Output is correct
25 Correct 779 ms 100044 KB Output is correct
26 Correct 480 ms 86820 KB Output is correct
27 Correct 445 ms 86244 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 61900 KB Output is correct
2 Correct 73 ms 63096 KB Output is correct
3 Correct 65 ms 63164 KB Output is correct
4 Correct 80 ms 63408 KB Output is correct
5 Correct 72 ms 63696 KB Output is correct
6 Correct 64 ms 62928 KB Output is correct
7 Correct 52 ms 61900 KB Output is correct
8 Correct 221 ms 80780 KB Output is correct
9 Correct 248 ms 80828 KB Output is correct
10 Correct 53 ms 61884 KB Output is correct
11 Correct 444 ms 106512 KB Output is correct
12 Correct 458 ms 106356 KB Output is correct
13 Correct 474 ms 118976 KB Output is correct
14 Correct 51 ms 61868 KB Output is correct
15 Correct 335 ms 97284 KB Output is correct
16 Correct 327 ms 87884 KB Output is correct
17 Correct 612 ms 93568 KB Output is correct
18 Correct 571 ms 92444 KB Output is correct
19 Correct 1183 ms 107628 KB Output is correct
20 Correct 1362 ms 106912 KB Output is correct
21 Correct 226 ms 82240 KB Output is correct
22 Correct 250 ms 82748 KB Output is correct
23 Correct 292 ms 88748 KB Output is correct
24 Correct 298 ms 89932 KB Output is correct
25 Correct 779 ms 100044 KB Output is correct
26 Correct 480 ms 86820 KB Output is correct
27 Correct 445 ms 86244 KB Output is correct
28 Correct 55 ms 61772 KB Output is correct
29 Correct 94 ms 62808 KB Output is correct
30 Correct 145 ms 62924 KB Output is correct
31 Correct 160 ms 63180 KB Output is correct
32 Correct 122 ms 63332 KB Output is correct
33 Correct 272 ms 62788 KB Output is correct
34 Correct 51 ms 61772 KB Output is correct
35 Execution timed out 3555 ms 80700 KB Time limit exceeded
36 Halted 0 ms 0 KB -