oj.uz

Submission #983609

# Submission time Handle Problem Language Result Execution time Memory
983609 2024-05-15T18:57:37 Z OAleksa Inside information (BOI21_servers) C++14
50 / 100
 270 ms 72444 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 120069;
const int K = 20;
int up[N][K], mx[N][K], is[N][K], dd[N][K], mn[N][K];
int timer, tin[N], tout[N], dep[N], par[N];
int n, k;
vector<pair<int, int>> g[N];
void dfs(int v, int p) {
	tin[v] = ++timer;
	dep[v] = dep[p] + 1;
	up[v][0] = p;
	for (int i = 1;i < K;i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
		mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
		mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
		is[v][i] = (is[v][i - 1] && is[up[v][i - 1]][i - 1] && mx[v][i - 1] < mx[up[v][i - 1]][0]);
		dd[v][i] = (dd[v][i - 1] && dd[up[v][i - 1]][i - 1] && mn[v][i - 1] > mn[up[v][i - 1]][0]);
	}
	for (auto u : g[v]) {
		if (u.f == p)
			continue;
		mx[u.f][0] = mn[u.f][0] = u.s;
		is[u.f][0] = dd[u.f][0] = 1;
		dfs(u.f, v);
	}
	tout[v] = timer;
}
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
int Up(int a, int b) {
	assert(anc(b, a));
	int d = dep[a] - dep[b];
	int r = 1;
	for (int i = 0;i < K;i++) {
		if (d >> i & 1) {
			int t = 1;
			d ^= (1 << i);
			if (d > 0)
				t &= (mx[a][i] < mx[up[a][i]][0]);
			r &= (is[a][i] & t);
			a = up[a][i];
		}
	}
	return r;
}
int Down(int a, int b) {
	assert(anc(b, a));
	int d = dep[a] - dep[b];
	int r = 1;
	for (int i = 0;i < K;i++) {
		if (d >> i & 1) {
			int t = 1;
			d ^= (1 << i);
			if (d > 0)
				t &= (mn[a][i] > mn[up[a][i]][0]);
			r &= (dd[a][i] & t);
			a = up[a][i];
		}
	}
	return r;
}
int Mx(int a, int b) {
	assert(anc(b, a));
	int d = dep[a] - dep[b];
	int r = 0;
	for (int i = 0;i < K;i++) {
		if (d >> i & 1) {
			r = max(r, mx[a][i]);
			a = up[a][i];
		}
	}
	return r;
}
int Mn(int a, int b) {
	assert(anc(b, a));
	int d = dep[a] - dep[b];
	int r = 1e9;
	for (int i = 0;i < K;i++) {
		if (d >> i & 1) {
			r = min(r, mn[a][i]);
			a = up[a][i];
		}
	}
	return r;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {        
  	cin >> n >> k;
		vector<tuple<int, int, int>> qs;
  	for (int i = 1;i <= n - 1 + k;i++) {
  		char c;
  		cin >> c;
  		int a, b;
  		if (c == 'S') {
  			cin >> a >> b;
  			g[a].push_back({b, i});
  			g[b].push_back({a, i});
  		}
  		else if (c == 'Q') {
  			cin >> a >> b;
  			qs.push_back({a, b, i});
  		}
  		else {
  			cin >> a;
  			qs.push_back({a, -1, i});
  		}
  	}
  	dfs(1, 0);
  	assert(qs.size() == k);
		for (auto j : qs) {
			int a, b, c;
			tie(a, b, c) = j;
			if (b == -1) {
				cout << "0\n";
			}
			else {
				int lc = lca(a, b);
				//od b od lc rastuce
				int mx1 = Mx(b, lc);
				int mx2 = Mx(a, lc);
				int mn1 = Mn(a, lc);
				bool ok = (Up(b, lc) && Down(a, lc) && c > max(mx1, mx2) && mx1 < mn1);
				cout << (ok ? "yes" : "no") << '\n';
			}
		}
  }
  return 0; 
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from servers.cpp:1:
servers.cpp: In function 'int main()':
servers.cpp:129:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |    assert(qs.size() == k);
      |           ~~~~~~~~~~^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9464 KB Output is correct
2 Correct 50 ms 12752 KB Output is correct
3 Correct 47 ms 13104 KB Output is correct
4 Correct 62 ms 13012 KB Output is correct
5 Correct 49 ms 13272 KB Output is correct
6 Correct 46 ms 12800 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9464 KB Output is correct
2 Correct 50 ms 12752 KB Output is correct
3 Correct 47 ms 13104 KB Output is correct
4 Correct 62 ms 13012 KB Output is correct
5 Correct 49 ms 13272 KB Output is correct
6 Correct 46 ms 12800 KB Output is correct
7 Incorrect 46 ms 9472 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 37 ms 9420 KB Output is correct
2 Correct 168 ms 60440 KB Output is correct
3 Correct 187 ms 60280 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9420 KB Output is correct
2 Correct 168 ms 60440 KB Output is correct
3 Correct 187 ms 60280 KB Output is correct
4 Incorrect 36 ms 9408 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 31 ms 9412 KB Output is correct
2 Correct 143 ms 72128 KB Output is correct
3 Correct 141 ms 72192 KB Output is correct
4 Correct 192 ms 72192 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9412 KB Output is correct
2 Correct 143 ms 72128 KB Output is correct
3 Correct 141 ms 72192 KB Output is correct
4 Correct 192 ms 72192 KB Output is correct
5 Incorrect 30 ms 9416 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 36 ms 9408 KB Output is correct
2 Correct 188 ms 60520 KB Output is correct
3 Correct 134 ms 60936 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9408 KB Output is correct
2 Correct 188 ms 60520 KB Output is correct
3 Correct 134 ms 60936 KB Output is correct
4 Incorrect 36 ms 9412 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 32 ms 9412 KB Output is correct
2 Correct 154 ms 72444 KB Output is correct
3 Correct 140 ms 72192 KB Output is correct
4 Correct 206 ms 72200 KB Output is correct
5 Correct 37 ms 9424 KB Output is correct
6 Correct 165 ms 61784 KB Output is correct
7 Correct 135 ms 62216 KB Output is correct
8 Correct 208 ms 62980 KB Output is correct
9 Correct 183 ms 62908 KB Output is correct
10 Correct 182 ms 68004 KB Output is correct
11 Correct 270 ms 67056 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9412 KB Output is correct
2 Correct 154 ms 72444 KB Output is correct
3 Correct 140 ms 72192 KB Output is correct
4 Correct 206 ms 72200 KB Output is correct
5 Correct 37 ms 9424 KB Output is correct
6 Correct 165 ms 61784 KB Output is correct
7 Correct 135 ms 62216 KB Output is correct
8 Correct 208 ms 62980 KB Output is correct
9 Correct 183 ms 62908 KB Output is correct
10 Correct 182 ms 68004 KB Output is correct
11 Correct 270 ms 67056 KB Output is correct
12 Incorrect 30 ms 9416 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 38 ms 9464 KB Output is correct
2 Correct 51 ms 12832 KB Output is correct
3 Correct 46 ms 12928 KB Output is correct
4 Correct 64 ms 13012 KB Output is correct
5 Correct 57 ms 13308 KB Output is correct
6 Correct 51 ms 12780 KB Output is correct
7 Correct 37 ms 9420 KB Output is correct
8 Correct 182 ms 60288 KB Output is correct
9 Correct 193 ms 60432 KB Output is correct
10 Correct 31 ms 9300 KB Output is correct
11 Correct 144 ms 72232 KB Output is correct
12 Correct 141 ms 72196 KB Output is correct
13 Correct 186 ms 72084 KB Output is correct
14 Correct 36 ms 9412 KB Output is correct
15 Correct 166 ms 61700 KB Output is correct
16 Correct 141 ms 62212 KB Output is correct
17 Correct 201 ms 62724 KB Output is correct
18 Correct 159 ms 62628 KB Output is correct
19 Correct 182 ms 68028 KB Output is correct
20 Correct 263 ms 67324 KB Output is correct
21 Correct 167 ms 61900 KB Output is correct
22 Correct 174 ms 62032 KB Output is correct
23 Correct 193 ms 62400 KB Output is correct
24 Correct 170 ms 62212 KB Output is correct
25 Correct 180 ms 64524 KB Output is correct
26 Correct 133 ms 61748 KB Output is correct
27 Correct 121 ms 61804 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9464 KB Output is correct
2 Correct 51 ms 12832 KB Output is correct
3 Correct 46 ms 12928 KB Output is correct
4 Correct 64 ms 13012 KB Output is correct
5 Correct 57 ms 13308 KB Output is correct
6 Correct 51 ms 12780 KB Output is correct
7 Correct 37 ms 9420 KB Output is correct
8 Correct 182 ms 60288 KB Output is correct
9 Correct 193 ms 60432 KB Output is correct
10 Correct 31 ms 9300 KB Output is correct
11 Correct 144 ms 72232 KB Output is correct
12 Correct 141 ms 72196 KB Output is correct
13 Correct 186 ms 72084 KB Output is correct
14 Correct 36 ms 9412 KB Output is correct
15 Correct 166 ms 61700 KB Output is correct
16 Correct 141 ms 62212 KB Output is correct
17 Correct 201 ms 62724 KB Output is correct
18 Correct 159 ms 62628 KB Output is correct
19 Correct 182 ms 68028 KB Output is correct
20 Correct 263 ms 67324 KB Output is correct
21 Correct 167 ms 61900 KB Output is correct
22 Correct 174 ms 62032 KB Output is correct
23 Correct 193 ms 62400 KB Output is correct
24 Correct 170 ms 62212 KB Output is correct
25 Correct 180 ms 64524 KB Output is correct
26 Correct 133 ms 61748 KB Output is correct
27 Correct 121 ms 61804 KB Output is correct
28 Incorrect 38 ms 9568 KB Extra information in the output file
29 Halted 0 ms 0 KB -