oj.uz

Submission #983589

# Submission time Handle Problem Language Result Execution time Memory
983589 2024-05-15T18:46:56 Z OAleksa Inside information (BOI21_servers) C++14
5 / 100
 191 ms 58200 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 120069;
const int K = 18;
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];
string q1[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 &= (mn[a][i] < mn[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 &= (mx[a][i] > mx[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) {
				assert(false);
				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:130: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]
  130 |    assert(qs.size() == k);
      |           ~~~~~~~~~~^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12736 KB Output is correct
2 Correct 49 ms 13900 KB Output is correct
3 Correct 44 ms 14028 KB Output is correct
4 Correct 71 ms 13876 KB Output is correct
5 Correct 49 ms 14384 KB Output is correct
6 Correct 44 ms 14068 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12736 KB Output is correct
2 Correct 49 ms 13900 KB Output is correct
3 Correct 44 ms 14028 KB Output is correct
4 Correct 71 ms 13876 KB Output is correct
5 Correct 49 ms 14384 KB Output is correct
6 Correct 44 ms 14068 KB Output is correct
7 Runtime error 24 ms 24812 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12972 KB Output is correct
2 Correct 172 ms 57724 KB Output is correct
3 Correct 159 ms 57716 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12972 KB Output is correct
2 Correct 172 ms 57724 KB Output is correct
3 Correct 159 ms 57716 KB Output is correct
4 Runtime error 27 ms 25036 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 12804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 12804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12744 KB Output is correct
2 Correct 170 ms 57720 KB Output is correct
3 Incorrect 141 ms 58200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12744 KB Output is correct
2 Correct 170 ms 57720 KB Output is correct
3 Incorrect 141 ms 58200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 12732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 12732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12736 KB Output is correct
2 Correct 50 ms 13804 KB Output is correct
3 Correct 43 ms 13900 KB Output is correct
4 Correct 74 ms 13868 KB Output is correct
5 Correct 50 ms 14340 KB Output is correct
6 Correct 45 ms 13804 KB Output is correct
7 Correct 39 ms 12744 KB Output is correct
8 Correct 191 ms 57796 KB Output is correct
9 Correct 162 ms 57700 KB Output is correct
10 Incorrect 30 ms 12832 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12736 KB Output is correct
2 Correct 50 ms 13804 KB Output is correct
3 Correct 43 ms 13900 KB Output is correct
4 Correct 74 ms 13868 KB Output is correct
5 Correct 50 ms 14340 KB Output is correct
6 Correct 45 ms 13804 KB Output is correct
7 Correct 39 ms 12744 KB Output is correct
8 Correct 191 ms 57796 KB Output is correct
9 Correct 162 ms 57700 KB Output is correct
10 Incorrect 30 ms 12832 KB Output isn't correct
11 Halted 0 ms 0 KB -