oj.uz

Submission #558341

# Submission time Handle Problem Language Result Execution time Memory
558341 2022-05-07T06:34:05 Z cheissmart Inside information (BOI21_servers) C++14
100 / 100
 676 ms 116352 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);
}
int bit[N * 2];
void add(int pos, int val) {
	assert(pos > 0);
	for(; pos < N * 2; pos += pos & -pos)
		bit[pos] += val;
}
int qry(int pos) {
	int res = 0;
	for(; pos; pos -= pos & -pos)
		res += bit[pos];
	return res;
}

void go(V<pi> up, V<pi> down, int op) {
	sort(ALL(up), greater<>()), sort(ALL(down), greater<>());
	int j = 0;
	for(int i = 0; i < SZ(up); i++) {
		while(j < SZ(down) && down[j].F >= up[i].F)
			add(down[j++].S, op);
		ans[up[i].S] += qry(up[i].S);
	}
	for(int i = 0; i < j; i++) 
		add(down[i].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:156:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |  for(auto[v, i]:G[c]) if(!vis[v]) {
      |          ^
servers.cpp:175:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  175 |  for(auto[v, i]:G[c]) if(!vis[v])
      |          ^
servers.cpp: In function 'int main()':
servers.cpp:208:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |  for(auto[u, v, i] : qq) {
      |          ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 83808 KB Output is correct
2 Correct 93 ms 83840 KB Output is correct
3 Correct 78 ms 83832 KB Output is correct
4 Correct 98 ms 83836 KB Output is correct
5 Correct 85 ms 84280 KB Output is correct
6 Correct 80 ms 84008 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 83808 KB Output is correct
2 Correct 93 ms 83840 KB Output is correct
3 Correct 78 ms 83832 KB Output is correct
4 Correct 98 ms 83836 KB Output is correct
5 Correct 85 ms 84280 KB Output is correct
6 Correct 80 ms 84008 KB Output is correct
7 Correct 78 ms 84196 KB Output is correct
8 Correct 87 ms 85028 KB Output is correct
9 Correct 79 ms 85268 KB Output is correct
10 Correct 92 ms 84864 KB Output is correct
11 Correct 87 ms 84716 KB Output is correct
12 Correct 78 ms 85552 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 82964 KB Output is correct
2 Correct 202 ms 99644 KB Output is correct
3 Correct 198 ms 99640 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 82964 KB Output is correct
2 Correct 202 ms 99644 KB Output is correct
3 Correct 198 ms 99640 KB Output is correct
4 Correct 68 ms 83716 KB Output is correct
5 Correct 255 ms 102428 KB Output is correct
6 Correct 160 ms 103624 KB Output is correct
7 Correct 172 ms 104980 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 83040 KB Output is correct
2 Correct 322 ms 108364 KB Output is correct
3 Correct 328 ms 108356 KB Output is correct
4 Correct 331 ms 109860 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 83040 KB Output is correct
2 Correct 322 ms 108364 KB Output is correct
3 Correct 328 ms 108356 KB Output is correct
4 Correct 331 ms 109860 KB Output is correct
5 Correct 71 ms 83652 KB Output is correct
6 Correct 376 ms 111612 KB Output is correct
7 Correct 411 ms 113252 KB Output is correct
8 Correct 382 ms 112564 KB Output is correct
9 Correct 389 ms 112640 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 83020 KB Output is correct
2 Correct 330 ms 99548 KB Output is correct
3 Correct 267 ms 98556 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 83020 KB Output is correct
2 Correct 330 ms 99548 KB Output is correct
3 Correct 267 ms 98556 KB Output is correct
4 Correct 70 ms 83648 KB Output is correct
5 Correct 438 ms 102948 KB Output is correct
6 Correct 314 ms 101168 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 83000 KB Output is correct
2 Correct 323 ms 108644 KB Output is correct
3 Correct 305 ms 108384 KB Output is correct
4 Correct 329 ms 109908 KB Output is correct
5 Correct 73 ms 83016 KB Output is correct
6 Correct 337 ms 99600 KB Output is correct
7 Correct 258 ms 98580 KB Output is correct
8 Correct 342 ms 98940 KB Output is correct
9 Correct 300 ms 99100 KB Output is correct
10 Correct 361 ms 104480 KB Output is correct
11 Correct 419 ms 103856 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 83000 KB Output is correct
2 Correct 323 ms 108644 KB Output is correct
3 Correct 305 ms 108384 KB Output is correct
4 Correct 329 ms 109908 KB Output is correct
5 Correct 73 ms 83016 KB Output is correct
6 Correct 337 ms 99600 KB Output is correct
7 Correct 258 ms 98580 KB Output is correct
8 Correct 342 ms 98940 KB Output is correct
9 Correct 300 ms 99100 KB Output is correct
10 Correct 361 ms 104480 KB Output is correct
11 Correct 419 ms 103856 KB Output is correct
12 Correct 69 ms 83596 KB Output is correct
13 Correct 363 ms 111636 KB Output is correct
14 Correct 411 ms 113276 KB Output is correct
15 Correct 395 ms 112384 KB Output is correct
16 Correct 376 ms 112476 KB Output is correct
17 Correct 74 ms 83648 KB Output is correct
18 Correct 449 ms 103192 KB Output is correct
19 Correct 310 ms 101140 KB Output is correct
20 Correct 360 ms 101952 KB Output is correct
21 Correct 335 ms 102220 KB Output is correct
22 Correct 458 ms 106720 KB Output is correct
23 Correct 666 ms 107132 KB Output is correct
24 Correct 541 ms 108592 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 82932 KB Output is correct
2 Correct 89 ms 83276 KB Output is correct
3 Correct 91 ms 83468 KB Output is correct
4 Correct 101 ms 83508 KB Output is correct
5 Correct 88 ms 83936 KB Output is correct
6 Correct 79 ms 83488 KB Output is correct
7 Correct 68 ms 82988 KB Output is correct
8 Correct 209 ms 99552 KB Output is correct
9 Correct 245 ms 99624 KB Output is correct
10 Correct 70 ms 82924 KB Output is correct
11 Correct 316 ms 108532 KB Output is correct
12 Correct 308 ms 108476 KB Output is correct
13 Correct 332 ms 110004 KB Output is correct
14 Correct 71 ms 82936 KB Output is correct
15 Correct 337 ms 99492 KB Output is correct
16 Correct 262 ms 98628 KB Output is correct
17 Correct 346 ms 99064 KB Output is correct
18 Correct 294 ms 99128 KB Output is correct
19 Correct 361 ms 104488 KB Output is correct
20 Correct 414 ms 103804 KB Output is correct
21 Correct 222 ms 99684 KB Output is correct
22 Correct 217 ms 99260 KB Output is correct
23 Correct 253 ms 98688 KB Output is correct
24 Correct 251 ms 98672 KB Output is correct
25 Correct 349 ms 103304 KB Output is correct
26 Correct 291 ms 97928 KB Output is correct
27 Correct 299 ms 97984 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 82932 KB Output is correct
2 Correct 89 ms 83276 KB Output is correct
3 Correct 91 ms 83468 KB Output is correct
4 Correct 101 ms 83508 KB Output is correct
5 Correct 88 ms 83936 KB Output is correct
6 Correct 79 ms 83488 KB Output is correct
7 Correct 68 ms 82988 KB Output is correct
8 Correct 209 ms 99552 KB Output is correct
9 Correct 245 ms 99624 KB Output is correct
10 Correct 70 ms 82924 KB Output is correct
11 Correct 316 ms 108532 KB Output is correct
12 Correct 308 ms 108476 KB Output is correct
13 Correct 332 ms 110004 KB Output is correct
14 Correct 71 ms 82936 KB Output is correct
15 Correct 337 ms 99492 KB Output is correct
16 Correct 262 ms 98628 KB Output is correct
17 Correct 346 ms 99064 KB Output is correct
18 Correct 294 ms 99128 KB Output is correct
19 Correct 361 ms 104488 KB Output is correct
20 Correct 414 ms 103804 KB Output is correct
21 Correct 222 ms 99684 KB Output is correct
22 Correct 217 ms 99260 KB Output is correct
23 Correct 253 ms 98688 KB Output is correct
24 Correct 251 ms 98672 KB Output is correct
25 Correct 349 ms 103304 KB Output is correct
26 Correct 291 ms 97928 KB Output is correct
27 Correct 299 ms 97984 KB Output is correct
28 Correct 75 ms 83744 KB Output is correct
29 Correct 88 ms 84956 KB Output is correct
30 Correct 79 ms 85288 KB Output is correct
31 Correct 95 ms 84868 KB Output is correct
32 Correct 89 ms 84716 KB Output is correct
33 Correct 79 ms 85400 KB Output is correct
34 Correct 71 ms 83836 KB Output is correct
35 Correct 207 ms 102448 KB Output is correct
36 Correct 159 ms 103712 KB Output is correct
37 Correct 178 ms 104968 KB Output is correct
38 Correct 69 ms 84516 KB Output is correct
39 Correct 366 ms 114628 KB Output is correct
40 Correct 411 ms 116352 KB Output is correct
41 Correct 381 ms 115040 KB Output is correct
42 Correct 381 ms 115036 KB Output is correct
43 Correct 76 ms 84540 KB Output is correct
44 Correct 434 ms 105864 KB Output is correct
45 Correct 351 ms 104144 KB Output is correct
46 Correct 387 ms 104672 KB Output is correct
47 Correct 349 ms 105264 KB Output is correct
48 Correct 459 ms 109332 KB Output is correct
49 Correct 676 ms 110052 KB Output is correct
50 Correct 550 ms 108688 KB Output is correct
51 Correct 203 ms 106804 KB Output is correct
52 Correct 203 ms 105744 KB Output is correct
53 Correct 174 ms 105632 KB Output is correct
54 Correct 174 ms 106616 KB Output is correct
55 Correct 181 ms 106672 KB Output is correct
56 Correct 245 ms 104460 KB Output is correct
57 Correct 341 ms 109620 KB Output is correct
58 Correct 473 ms 105320 KB Output is correct
59 Correct 331 ms 103312 KB Output is correct