oj.uz

Submission #558334

# Submission time Handle Problem Language Result Execution time Memory
558334 2022-05-07T06:17:19 Z cheissmart Inside information (BOI21_servers) C++14
50 / 100
 441 ms 110156 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;

V<pi> G[N];

namespace he {

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

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

}

namespace be {

vi aux[N];
int ans[N * 2], sz[N];
bool vis[N];

void dfs_sz(int u, int p = 0) {
	sz[u] = 1;
	for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
}

void dfs_c(int u, int& c, int tot, int p = 0) {
	int mx = tot - sz[u];
	for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
		dfs_c(v, c, tot, u);
		mx = max(mx, sz[v]);
	}
	if(mx * 2 <= tot) c = u;
}

void dfs_down(int u, V<pi>&down, int l, int r, int p) {
	down.EB(l, r);
	for(auto[v, i] : G[u]) if(v != p && !vis[v])
		if(i > r)
			dfs_down(v, down, l, i, u);
}

void dfs_up(int u, V<pi>&up, int l, int r, int p) {
	for(int i:aux[u]) if(i >= r) {
		up.EB(r, i);
		ans[i]++; // to c
	}
	for(auto[v, i] : G[u]) if(v != p && !vis[v])
		if(i < l)
			dfs_up(v, up, i, r, u);
}

void go(V<pi> up, V<pi> down, int op) {
	// for(pi p:up) {
	// 	for(pi pp:down) {
	// 		if(p.F <= pp.F && pp.S <= p.S)
	// 			ans[p.S] += op;
	// 	}
	// }
}

void CD(int u) {
	dfs_sz(u);
	int c = -1; dfs_c(u, c, sz[u]);
	V<pi> down_all, up_all;

	for(auto[v, i]:G[c]) if(!vis[v]) {
		V<pi> down;
		dfs_down(v, down, i, i, c);
		V<pi> up;
		dfs_up(v, up, i, i, c);
		go(up, down, -1);

		for(pi p:up) up_all.PB(p);
		for(pi p:down) down_all.PB(p);
	}
	go(up_all, down_all, 1);

	V<pi> upc;
	for(int i:aux[c])
		upc.EB(0, i);

	go(upc, down_all, 1);

	vis[c] = 1;
	for(auto[v, i]:G[c]) if(!vis[v])
		CD(v);

}

}
	
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});
			be::aux[u].PB(i);
		}
	}
	he::dfs(1);

	be::CD(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 = he::lca(u, v);
			auto tt = he::go_up(v, he::d[v] - he::d[l]) + he::go_down(u, he::d[u] - he::d[l]);
			if(tt.mx < i && tt.ok)
				cout << "yes\n";
			else
				cout << "no\n";
		} else {
			cout << be::ans[i] + 1 << '\n';
		}
	}

}

Compilation message

servers.cpp: In function 'void he::dfs(int, int)':
servers.cpp:52:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |  for(auto[v, i]:G[u]) if(v != pa) {
      |          ^
servers.cpp: In function 'void be::dfs_sz(int, int)':
servers.cpp:95:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |  for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
      |          ^
servers.cpp: In function 'void be::dfs_c(int, int&, int, int)':
servers.cpp:103:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |  for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
      |          ^
servers.cpp: In function 'void be::dfs_down(int, std::vector<std::pair<int, int> >&, int, int, int)':
servers.cpp:112:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |  for(auto[v, i] : G[u]) if(v != p && !vis[v])
      |          ^
servers.cpp: In function 'void be::dfs_up(int, std::vector<std::pair<int, int> >&, int, int, int)':
servers.cpp:122:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |  for(auto[v, i] : G[u]) if(v != p && !vis[v])
      |          ^
servers.cpp: In function 'void be::CD(int)':
servers.cpp:141:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |  for(auto[v, i]:G[c]) if(!vis[v]) {
      |          ^
servers.cpp:160:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  160 |  for(auto[v, i]:G[c]) if(!vis[v])
      |          ^
servers.cpp: In function 'int main()':
servers.cpp:193:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  193 |  for(auto[u, v, i] : qq) {
      |          ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83352 KB Output is correct
2 Correct 92 ms 83556 KB Output is correct
3 Correct 82 ms 83784 KB Output is correct
4 Correct 99 ms 83796 KB Output is correct
5 Correct 91 ms 84048 KB Output is correct
6 Correct 80 ms 83788 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83352 KB Output is correct
2 Correct 92 ms 83556 KB Output is correct
3 Correct 82 ms 83784 KB Output is correct
4 Correct 99 ms 83796 KB Output is correct
5 Correct 91 ms 84048 KB Output is correct
6 Correct 80 ms 83788 KB Output is correct
7 Incorrect 76 ms 83472 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 73 ms 83228 KB Output is correct
2 Correct 213 ms 99884 KB Output is correct
3 Correct 203 ms 99872 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83228 KB Output is correct
2 Correct 213 ms 99884 KB Output is correct
3 Correct 203 ms 99872 KB Output is correct
4 Incorrect 71 ms 83436 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 77 ms 83236 KB Output is correct
2 Correct 321 ms 108812 KB Output is correct
3 Correct 317 ms 108612 KB Output is correct
4 Correct 296 ms 110156 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 83236 KB Output is correct
2 Correct 321 ms 108812 KB Output is correct
3 Correct 317 ms 108612 KB Output is correct
4 Correct 296 ms 110156 KB Output is correct
5 Incorrect 72 ms 83392 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 77 ms 83268 KB Output is correct
2 Correct 291 ms 99732 KB Output is correct
3 Correct 268 ms 98784 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 83268 KB Output is correct
2 Correct 291 ms 99732 KB Output is correct
3 Correct 268 ms 98784 KB Output is correct
4 Incorrect 73 ms 83288 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 73 ms 83008 KB Output is correct
2 Correct 314 ms 108352 KB Output is correct
3 Correct 310 ms 108424 KB Output is correct
4 Correct 296 ms 109820 KB Output is correct
5 Correct 73 ms 83024 KB Output is correct
6 Correct 260 ms 99528 KB Output is correct
7 Correct 262 ms 98588 KB Output is correct
8 Correct 384 ms 98908 KB Output is correct
9 Correct 294 ms 98956 KB Output is correct
10 Correct 352 ms 104552 KB Output is correct
11 Correct 441 ms 103808 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83008 KB Output is correct
2 Correct 314 ms 108352 KB Output is correct
3 Correct 310 ms 108424 KB Output is correct
4 Correct 296 ms 109820 KB Output is correct
5 Correct 73 ms 83024 KB Output is correct
6 Correct 260 ms 99528 KB Output is correct
7 Correct 262 ms 98588 KB Output is correct
8 Correct 384 ms 98908 KB Output is correct
9 Correct 294 ms 98956 KB Output is correct
10 Correct 352 ms 104552 KB Output is correct
11 Correct 441 ms 103808 KB Output is correct
12 Incorrect 69 ms 83236 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 77 ms 82968 KB Output is correct
2 Correct 91 ms 83296 KB Output is correct
3 Correct 82 ms 83504 KB Output is correct
4 Correct 99 ms 83428 KB Output is correct
5 Correct 88 ms 83932 KB Output is correct
6 Correct 79 ms 83552 KB Output is correct
7 Correct 73 ms 83040 KB Output is correct
8 Correct 199 ms 99556 KB Output is correct
9 Correct 197 ms 99616 KB Output is correct
10 Correct 68 ms 82908 KB Output is correct
11 Correct 305 ms 108388 KB Output is correct
12 Correct 319 ms 108344 KB Output is correct
13 Correct 295 ms 109884 KB Output is correct
14 Correct 76 ms 82928 KB Output is correct
15 Correct 255 ms 99584 KB Output is correct
16 Correct 256 ms 98560 KB Output is correct
17 Correct 334 ms 98948 KB Output is correct
18 Correct 288 ms 98940 KB Output is correct
19 Correct 347 ms 104464 KB Output is correct
20 Correct 413 ms 103740 KB Output is correct
21 Correct 211 ms 99628 KB Output is correct
22 Correct 232 ms 99148 KB Output is correct
23 Correct 248 ms 98596 KB Output is correct
24 Correct 246 ms 98616 KB Output is correct
25 Correct 345 ms 103284 KB Output is correct
26 Correct 295 ms 97928 KB Output is correct
27 Correct 284 ms 97980 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 77 ms 82968 KB Output is correct
2 Correct 91 ms 83296 KB Output is correct
3 Correct 82 ms 83504 KB Output is correct
4 Correct 99 ms 83428 KB Output is correct
5 Correct 88 ms 83932 KB Output is correct
6 Correct 79 ms 83552 KB Output is correct
7 Correct 73 ms 83040 KB Output is correct
8 Correct 199 ms 99556 KB Output is correct
9 Correct 197 ms 99616 KB Output is correct
10 Correct 68 ms 82908 KB Output is correct
11 Correct 305 ms 108388 KB Output is correct
12 Correct 319 ms 108344 KB Output is correct
13 Correct 295 ms 109884 KB Output is correct
14 Correct 76 ms 82928 KB Output is correct
15 Correct 255 ms 99584 KB Output is correct
16 Correct 256 ms 98560 KB Output is correct
17 Correct 334 ms 98948 KB Output is correct
18 Correct 288 ms 98940 KB Output is correct
19 Correct 347 ms 104464 KB Output is correct
20 Correct 413 ms 103740 KB Output is correct
21 Correct 211 ms 99628 KB Output is correct
22 Correct 232 ms 99148 KB Output is correct
23 Correct 248 ms 98596 KB Output is correct
24 Correct 246 ms 98616 KB Output is correct
25 Correct 345 ms 103284 KB Output is correct
26 Correct 295 ms 97928 KB Output is correct
27 Correct 284 ms 97980 KB Output is correct
28 Incorrect 75 ms 83212 KB Extra information in the output file
29 Halted 0 ms 0 KB -