oj.uz

Submission #585892

# Submission time Handle Problem Language Result Execution time Memory
585892 2022-06-29T13:57:34 Z pavement Inside information (BOI21_servers) C++17
50 / 100
 341 ms 95296 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, A[240005], B[240005], inc[240005], down[240005], dep[240005], anc[25][240005], wei[25][240005];
char C[240005];
vector<ii> adj[240005];

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];
}

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);
	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') {
			
		}
	}
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 56136 KB Output is correct
2 Correct 58 ms 57204 KB Output is correct
3 Correct 52 ms 57336 KB Output is correct
4 Correct 72 ms 57552 KB Output is correct
5 Correct 60 ms 57812 KB Output is correct
6 Correct 52 ms 57164 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 56136 KB Output is correct
2 Correct 58 ms 57204 KB Output is correct
3 Correct 52 ms 57336 KB Output is correct
4 Correct 72 ms 57552 KB Output is correct
5 Correct 60 ms 57812 KB Output is correct
6 Correct 52 ms 57164 KB Output is correct
7 Incorrect 46 ms 56136 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 56224 KB Output is correct
2 Correct 196 ms 70492 KB Output is correct
3 Correct 187 ms 70516 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 56224 KB Output is correct
2 Correct 196 ms 70492 KB Output is correct
3 Correct 187 ms 70516 KB Output is correct
4 Incorrect 44 ms 56172 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56140 KB Output is correct
2 Correct 165 ms 95296 KB Output is correct
3 Correct 144 ms 95204 KB Output is correct
4 Correct 180 ms 94312 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56140 KB Output is correct
2 Correct 165 ms 95296 KB Output is correct
3 Correct 144 ms 95204 KB Output is correct
4 Correct 180 ms 94312 KB Output is correct
5 Incorrect 46 ms 56252 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56272 KB Output is correct
2 Correct 168 ms 75412 KB Output is correct
3 Correct 134 ms 75640 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56272 KB Output is correct
2 Correct 168 ms 75412 KB Output is correct
3 Correct 134 ms 75640 KB Output is correct
4 Incorrect 46 ms 56268 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56256 KB Output is correct
2 Correct 153 ms 95096 KB Output is correct
3 Correct 158 ms 95096 KB Output is correct
4 Correct 186 ms 94404 KB Output is correct
5 Correct 50 ms 56196 KB Output is correct
6 Correct 151 ms 75344 KB Output is correct
7 Correct 135 ms 75716 KB Output is correct
8 Correct 238 ms 81788 KB Output is correct
9 Correct 199 ms 80704 KB Output is correct
10 Correct 240 ms 91448 KB Output is correct
11 Correct 323 ms 90820 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56256 KB Output is correct
2 Correct 153 ms 95096 KB Output is correct
3 Correct 158 ms 95096 KB Output is correct
4 Correct 186 ms 94404 KB Output is correct
5 Correct 50 ms 56196 KB Output is correct
6 Correct 151 ms 75344 KB Output is correct
7 Correct 135 ms 75716 KB Output is correct
8 Correct 238 ms 81788 KB Output is correct
9 Correct 199 ms 80704 KB Output is correct
10 Correct 240 ms 91448 KB Output is correct
11 Correct 323 ms 90820 KB Output is correct
12 Incorrect 43 ms 56140 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56224 KB Output is correct
2 Correct 63 ms 57284 KB Output is correct
3 Correct 58 ms 57244 KB Output is correct
4 Correct 70 ms 57576 KB Output is correct
5 Correct 65 ms 57848 KB Output is correct
6 Correct 53 ms 57160 KB Output is correct
7 Correct 46 ms 56208 KB Output is correct
8 Correct 173 ms 70604 KB Output is correct
9 Correct 171 ms 70496 KB Output is correct
10 Correct 50 ms 56204 KB Output is correct
11 Correct 145 ms 95188 KB Output is correct
12 Correct 154 ms 95296 KB Output is correct
13 Correct 181 ms 94384 KB Output is correct
14 Correct 50 ms 56116 KB Output is correct
15 Correct 162 ms 75320 KB Output is correct
16 Correct 139 ms 75668 KB Output is correct
17 Correct 237 ms 81688 KB Output is correct
18 Correct 204 ms 80812 KB Output is correct
19 Correct 258 ms 91468 KB Output is correct
20 Correct 341 ms 90760 KB Output is correct
21 Correct 195 ms 72020 KB Output is correct
22 Correct 185 ms 71960 KB Output is correct
23 Correct 197 ms 76492 KB Output is correct
24 Correct 204 ms 77596 KB Output is correct
25 Correct 234 ms 88036 KB Output is correct
26 Correct 162 ms 75864 KB Output is correct
27 Correct 165 ms 75476 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56224 KB Output is correct
2 Correct 63 ms 57284 KB Output is correct
3 Correct 58 ms 57244 KB Output is correct
4 Correct 70 ms 57576 KB Output is correct
5 Correct 65 ms 57848 KB Output is correct
6 Correct 53 ms 57160 KB Output is correct
7 Correct 46 ms 56208 KB Output is correct
8 Correct 173 ms 70604 KB Output is correct
9 Correct 171 ms 70496 KB Output is correct
10 Correct 50 ms 56204 KB Output is correct
11 Correct 145 ms 95188 KB Output is correct
12 Correct 154 ms 95296 KB Output is correct
13 Correct 181 ms 94384 KB Output is correct
14 Correct 50 ms 56116 KB Output is correct
15 Correct 162 ms 75320 KB Output is correct
16 Correct 139 ms 75668 KB Output is correct
17 Correct 237 ms 81688 KB Output is correct
18 Correct 204 ms 80812 KB Output is correct
19 Correct 258 ms 91468 KB Output is correct
20 Correct 341 ms 90760 KB Output is correct
21 Correct 195 ms 72020 KB Output is correct
22 Correct 185 ms 71960 KB Output is correct
23 Correct 197 ms 76492 KB Output is correct
24 Correct 204 ms 77596 KB Output is correct
25 Correct 234 ms 88036 KB Output is correct
26 Correct 162 ms 75864 KB Output is correct
27 Correct 165 ms 75476 KB Output is correct
28 Incorrect 47 ms 56164 KB Extra information in the output file
29 Halted 0 ms 0 KB -