oj.uz

Submission #558246

# Submission time Handle Problem Language Result Execution time Memory
558246 2022-05-07T05:04:36 Z cheissmart Inside information (BOI21_servers) C++14
50 / 100
 350 ms 162580 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 120005;

struct Data {
	bool ok;
	int l, r;
	int mx;
	Data(int _mx = -1) {
		ok = true;
		l = r = mx = _mx;
	}
	friend Data operator + (const Data lhs, const Data rhs) {
		if(lhs.mx == -1) return rhs;
		if(rhs.mx == -1) return lhs;
		Data res;
		res.ok = lhs.ok & rhs.ok & (lhs.r < rhs.l);
		res.l = lhs.l, res.r = rhs.r;
		res.mx = max(lhs.mx, rhs.mx);
		return res;
	}
} up[N][20], down[N][20];

V<pi> G[N];
int p[N][20], d[N];

void dfs(int u, int pa = 0) {
	p[u][0] = pa;
	for(int i = 1; i < 20; i++) {
		p[u][i] = p[p[u][i - 1]][i - 1];
		up[u][i] = up[u][i - 1] + up[p[u][i - 1]][i - 1];
		down[u][i] = down[p[u][i - 1]][i - 1] + down[u][i - 1];
	}
	for(auto[v, i]:G[u]) if(v != pa) {
		d[v] = d[u] + 1;
		up[v][0] = down[v][0] = Data(i);
		dfs(v, u);
	}
}

int lca(int u, int v) {
	if(d[u] > d[v]) swap(u, v);
	for(int i = 0; i < 20; i++)
		if((d[v] - d[u]) >> i & 1)
			v = p[v][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--)
		if(p[u][i] != p[v][i])
			u = p[u][i], v = p[v][i];
	assert(u != v && p[u][0] == p[v][0]);
	return p[u][0];
}

Data go_up(int u, int step) {
	Data res;
	for(int i = 0; i < 20; i++) if(step >> i & 1)
		res = res + up[u][i], u = p[u][i];
	return res;
}
Data go_down(int u, int step) {
	Data res;
	for(int i = 0; i < 20; i++) if(step >> i & 1)
		res = down[u][i] + res, u = p[u][i];
	return res;
}

signed main()
{
	IO_OP;

	int n, k;
	cin >> n >> k;
	V<array<int, 3>> qq;
	for(int i = 1; i <= n + k - 1; i++) {
		char op; cin >> op;
		if(op == 'S') {
			int u, v; cin >> u >> v;
			G[u].EB(v, i);
			G[v].EB(u, i);
		} else if(op == 'Q') {
			int u, v; cin >> u >> v;
			qq.PB({u, v, i});
		} else {
			int u; cin >> u;
			qq.PB({u, -1, i});
		}
	}
	dfs(1);
	for(auto[u, v, i] : qq) {
		if(v != -1) {
			// is the path v -> u increasing?
			if(u == v) {
				cout << "yes\n";
				continue;
			}
			int l = lca(u, v);
			Data tt = go_up(v, d[v] - d[l]) + go_down(u, d[u] - d[l]);
			if(tt.mx < i && tt.ok)
				cout << "yes\n";
			else
				cout << "no\n";
		} else {
			throw;
		}
	}

}

Compilation message

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:49:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |  for(auto[v, i]:G[u]) if(v != pa) {
      |          ^
servers.cpp: In function 'int main()':
servers.cpp:104:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |  for(auto[u, v, i] : qq) {
      |          ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 93 ms 80164 KB Output is correct
2 Correct 89 ms 81868 KB Output is correct
3 Correct 83 ms 81988 KB Output is correct
4 Correct 99 ms 82040 KB Output is correct
5 Correct 96 ms 82360 KB Output is correct
6 Correct 80 ms 81972 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 93 ms 80164 KB Output is correct
2 Correct 89 ms 81868 KB Output is correct
3 Correct 83 ms 81988 KB Output is correct
4 Correct 99 ms 82040 KB Output is correct
5 Correct 96 ms 82360 KB Output is correct
6 Correct 80 ms 81972 KB Output is correct
7 Runtime error 120 ms 162568 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 71 ms 80208 KB Output is correct
2 Correct 237 ms 94672 KB Output is correct
3 Correct 176 ms 94576 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 71 ms 80208 KB Output is correct
2 Correct 237 ms 94672 KB Output is correct
3 Correct 176 ms 94576 KB Output is correct
4 Runtime error 113 ms 161620 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 80116 KB Output is correct
2 Correct 282 ms 108296 KB Output is correct
3 Correct 206 ms 108244 KB Output is correct
4 Correct 235 ms 108224 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 80116 KB Output is correct
2 Correct 282 ms 108296 KB Output is correct
3 Correct 206 ms 108244 KB Output is correct
4 Correct 235 ms 108224 KB Output is correct
5 Runtime error 132 ms 162492 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 80192 KB Output is correct
2 Correct 221 ms 97924 KB Output is correct
3 Correct 199 ms 98312 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 80192 KB Output is correct
2 Correct 221 ms 97924 KB Output is correct
3 Correct 199 ms 98312 KB Output is correct
4 Runtime error 132 ms 162552 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 71 ms 80208 KB Output is correct
2 Correct 206 ms 108280 KB Output is correct
3 Correct 226 ms 108332 KB Output is correct
4 Correct 255 ms 108248 KB Output is correct
5 Correct 74 ms 81028 KB Output is correct
6 Correct 225 ms 97900 KB Output is correct
7 Correct 177 ms 98428 KB Output is correct
8 Correct 262 ms 98788 KB Output is correct
9 Correct 223 ms 98788 KB Output is correct
10 Correct 241 ms 104072 KB Output is correct
11 Correct 325 ms 103148 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 71 ms 80208 KB Output is correct
2 Correct 206 ms 108280 KB Output is correct
3 Correct 226 ms 108332 KB Output is correct
4 Correct 255 ms 108248 KB Output is correct
5 Correct 74 ms 81028 KB Output is correct
6 Correct 225 ms 97900 KB Output is correct
7 Correct 177 ms 98428 KB Output is correct
8 Correct 262 ms 98788 KB Output is correct
9 Correct 223 ms 98788 KB Output is correct
10 Correct 241 ms 104072 KB Output is correct
11 Correct 325 ms 103148 KB Output is correct
12 Runtime error 118 ms 162452 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 77 ms 80188 KB Output is correct
2 Correct 93 ms 81836 KB Output is correct
3 Correct 82 ms 82044 KB Output is correct
4 Correct 115 ms 81956 KB Output is correct
5 Correct 97 ms 82328 KB Output is correct
6 Correct 86 ms 81944 KB Output is correct
7 Correct 74 ms 81088 KB Output is correct
8 Correct 199 ms 97512 KB Output is correct
9 Correct 197 ms 97520 KB Output is correct
10 Correct 73 ms 81088 KB Output is correct
11 Correct 258 ms 108340 KB Output is correct
12 Correct 224 ms 108256 KB Output is correct
13 Correct 243 ms 108200 KB Output is correct
14 Correct 77 ms 80972 KB Output is correct
15 Correct 197 ms 97928 KB Output is correct
16 Correct 207 ms 98352 KB Output is correct
17 Correct 260 ms 98760 KB Output is correct
18 Correct 254 ms 98756 KB Output is correct
19 Correct 242 ms 103980 KB Output is correct
20 Correct 350 ms 103200 KB Output is correct
21 Correct 189 ms 98020 KB Output is correct
22 Correct 183 ms 98140 KB Output is correct
23 Correct 222 ms 98248 KB Output is correct
24 Correct 225 ms 98356 KB Output is correct
25 Correct 230 ms 100720 KB Output is correct
26 Correct 194 ms 97852 KB Output is correct
27 Correct 173 ms 97984 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 77 ms 80188 KB Output is correct
2 Correct 93 ms 81836 KB Output is correct
3 Correct 82 ms 82044 KB Output is correct
4 Correct 115 ms 81956 KB Output is correct
5 Correct 97 ms 82328 KB Output is correct
6 Correct 86 ms 81944 KB Output is correct
7 Correct 74 ms 81088 KB Output is correct
8 Correct 199 ms 97512 KB Output is correct
9 Correct 197 ms 97520 KB Output is correct
10 Correct 73 ms 81088 KB Output is correct
11 Correct 258 ms 108340 KB Output is correct
12 Correct 224 ms 108256 KB Output is correct
13 Correct 243 ms 108200 KB Output is correct
14 Correct 77 ms 80972 KB Output is correct
15 Correct 197 ms 97928 KB Output is correct
16 Correct 207 ms 98352 KB Output is correct
17 Correct 260 ms 98760 KB Output is correct
18 Correct 254 ms 98756 KB Output is correct
19 Correct 242 ms 103980 KB Output is correct
20 Correct 350 ms 103200 KB Output is correct
21 Correct 189 ms 98020 KB Output is correct
22 Correct 183 ms 98140 KB Output is correct
23 Correct 222 ms 98248 KB Output is correct
24 Correct 225 ms 98356 KB Output is correct
25 Correct 230 ms 100720 KB Output is correct
26 Correct 194 ms 97852 KB Output is correct
27 Correct 173 ms 97984 KB Output is correct
28 Runtime error 119 ms 162580 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -