oj.uz

Submission #558335

# Submission time Handle Problem Language Result Execution time Memory
558335 2022-05-07T06:18:32 Z cheissmart Inside information (BOI21_servers) C++14
67.5 / 100
 3500 ms 115428 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) {
				if(p.S < 0 || p.S >= 2 * N)
					exit(0);
				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:144:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |  for(auto[v, i]:G[c]) if(!vis[v]) {
      |          ^
servers.cpp:163:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |  for(auto[v, i]:G[c]) if(!vis[v])
      |          ^
servers.cpp: In function 'int main()':
servers.cpp:196:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  196 |  for(auto[u, v, i] : qq) {
      |          ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 82928 KB Output is correct
2 Correct 88 ms 83380 KB Output is correct
3 Correct 78 ms 83512 KB Output is correct
4 Correct 102 ms 83528 KB Output is correct
5 Correct 95 ms 83808 KB Output is correct
6 Correct 77 ms 83680 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 82928 KB Output is correct
2 Correct 88 ms 83380 KB Output is correct
3 Correct 78 ms 83512 KB Output is correct
4 Correct 102 ms 83528 KB Output is correct
5 Correct 95 ms 83808 KB Output is correct
6 Correct 77 ms 83680 KB Output is correct
7 Correct 72 ms 83224 KB Output is correct
8 Correct 87 ms 85472 KB Output is correct
9 Correct 180 ms 85860 KB Output is correct
10 Correct 95 ms 85532 KB Output is correct
11 Correct 81 ms 85796 KB Output is correct
12 Correct 416 ms 86288 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 83008 KB Output is correct
2 Correct 210 ms 99564 KB Output is correct
3 Correct 202 ms 99584 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 83008 KB Output is correct
2 Correct 210 ms 99564 KB Output is correct
3 Correct 202 ms 99584 KB Output is correct
4 Correct 75 ms 83408 KB Output is correct
5 Correct 2275 ms 104292 KB Output is correct
6 Execution timed out 3592 ms 103752 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83004 KB Output is correct
2 Correct 370 ms 108428 KB Output is correct
3 Correct 375 ms 108364 KB Output is correct
4 Correct 300 ms 109824 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83004 KB Output is correct
2 Correct 370 ms 108428 KB Output is correct
3 Correct 375 ms 108364 KB Output is correct
4 Correct 300 ms 109824 KB Output is correct
5 Correct 66 ms 83140 KB Output is correct
6 Correct 405 ms 113696 KB Output is correct
7 Correct 3344 ms 115428 KB Output is correct
8 Correct 425 ms 114020 KB Output is correct
9 Correct 400 ms 114092 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83000 KB Output is correct
2 Correct 279 ms 99524 KB Output is correct
3 Correct 305 ms 98644 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 83000 KB Output is correct
2 Correct 279 ms 99524 KB Output is correct
3 Correct 305 ms 98644 KB Output is correct
4 Correct 71 ms 83240 KB Output is correct
5 Correct 3091 ms 105188 KB Output is correct
6 Correct 337 ms 103108 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 83004 KB Output is correct
2 Correct 342 ms 108372 KB Output is correct
3 Correct 363 ms 108320 KB Output is correct
4 Correct 331 ms 109776 KB Output is correct
5 Correct 80 ms 83064 KB Output is correct
6 Correct 268 ms 99512 KB Output is correct
7 Correct 355 ms 98532 KB Output is correct
8 Correct 368 ms 98940 KB Output is correct
9 Correct 320 ms 98984 KB Output is correct
10 Correct 398 ms 104560 KB Output is correct
11 Correct 461 ms 103768 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 83004 KB Output is correct
2 Correct 342 ms 108372 KB Output is correct
3 Correct 363 ms 108320 KB Output is correct
4 Correct 331 ms 109776 KB Output is correct
5 Correct 80 ms 83064 KB Output is correct
6 Correct 268 ms 99512 KB Output is correct
7 Correct 355 ms 98532 KB Output is correct
8 Correct 368 ms 98940 KB Output is correct
9 Correct 320 ms 98984 KB Output is correct
10 Correct 398 ms 104560 KB Output is correct
11 Correct 461 ms 103768 KB Output is correct
12 Correct 72 ms 83240 KB Output is correct
13 Correct 383 ms 113644 KB Output is correct
14 Correct 3381 ms 115352 KB Output is correct
15 Correct 391 ms 114120 KB Output is correct
16 Correct 389 ms 113988 KB Output is correct
17 Correct 77 ms 84100 KB Output is correct
18 Correct 3111 ms 105144 KB Output is correct
19 Correct 333 ms 103244 KB Output is correct
20 Correct 347 ms 104192 KB Output is correct
21 Correct 397 ms 104136 KB Output is correct
22 Correct 1208 ms 108408 KB Output is correct
23 Execution timed out 3531 ms 109108 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 75 ms 83004 KB Output is correct
2 Correct 95 ms 83328 KB Output is correct
3 Correct 88 ms 83528 KB Output is correct
4 Correct 107 ms 83444 KB Output is correct
5 Correct 89 ms 83864 KB Output is correct
6 Correct 82 ms 83528 KB Output is correct
7 Correct 70 ms 82948 KB Output is correct
8 Correct 234 ms 99568 KB Output is correct
9 Correct 209 ms 99544 KB Output is correct
10 Correct 67 ms 82912 KB Output is correct
11 Correct 370 ms 108368 KB Output is correct
12 Correct 343 ms 108440 KB Output is correct
13 Correct 354 ms 109928 KB Output is correct
14 Correct 87 ms 82984 KB Output is correct
15 Correct 268 ms 99580 KB Output is correct
16 Correct 273 ms 98636 KB Output is correct
17 Correct 404 ms 98844 KB Output is correct
18 Correct 326 ms 98956 KB Output is correct
19 Correct 432 ms 104500 KB Output is correct
20 Correct 447 ms 103808 KB Output is correct
21 Correct 289 ms 99628 KB Output is correct
22 Correct 217 ms 99200 KB Output is correct
23 Correct 295 ms 98700 KB Output is correct
24 Correct 253 ms 98692 KB Output is correct
25 Correct 414 ms 103288 KB Output is correct
26 Correct 306 ms 97928 KB Output is correct
27 Correct 346 ms 97928 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 75 ms 83004 KB Output is correct
2 Correct 95 ms 83328 KB Output is correct
3 Correct 88 ms 83528 KB Output is correct
4 Correct 107 ms 83444 KB Output is correct
5 Correct 89 ms 83864 KB Output is correct
6 Correct 82 ms 83528 KB Output is correct
7 Correct 70 ms 82948 KB Output is correct
8 Correct 234 ms 99568 KB Output is correct
9 Correct 209 ms 99544 KB Output is correct
10 Correct 67 ms 82912 KB Output is correct
11 Correct 370 ms 108368 KB Output is correct
12 Correct 343 ms 108440 KB Output is correct
13 Correct 354 ms 109928 KB Output is correct
14 Correct 87 ms 82984 KB Output is correct
15 Correct 268 ms 99580 KB Output is correct
16 Correct 273 ms 98636 KB Output is correct
17 Correct 404 ms 98844 KB Output is correct
18 Correct 326 ms 98956 KB Output is correct
19 Correct 432 ms 104500 KB Output is correct
20 Correct 447 ms 103808 KB Output is correct
21 Correct 289 ms 99628 KB Output is correct
22 Correct 217 ms 99200 KB Output is correct
23 Correct 295 ms 98700 KB Output is correct
24 Correct 253 ms 98692 KB Output is correct
25 Correct 414 ms 103288 KB Output is correct
26 Correct 306 ms 97928 KB Output is correct
27 Correct 346 ms 97928 KB Output is correct
28 Correct 81 ms 83364 KB Output is correct
29 Correct 92 ms 85348 KB Output is correct
30 Correct 164 ms 85884 KB Output is correct
31 Correct 97 ms 85500 KB Output is correct
32 Correct 89 ms 85852 KB Output is correct
33 Correct 406 ms 86420 KB Output is correct
34 Correct 81 ms 84160 KB Output is correct
35 Correct 2348 ms 104296 KB Output is correct
36 Execution timed out 3583 ms 103852 KB Time limit exceeded
37 Halted 0 ms 0 KB -