oj.uz

Submission #863618

# Submission time Handle Problem Language Result Execution time Memory
863618 2023-10-20T15:48:44 Z Mizo_Compiler Inside information (BOI21_servers) C++17
55 / 100
 3500 ms 36864 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast, O2, O3")
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 120001;
int n, pr[N], sz[N], q, dep[N], p[N][17], mn[N], vt[N];
int mx[N], sze[N], bit[N+N], ans[N+N];
bool r[N];
vector<array<int, 3>> qr;
vector<pair<int, int>> adj[N];
vector<int> c[N], ar;

void upd(int i, int val) {
	i++;
	while (i <= n+q) {
		bit[i] += val;
		i += (i & -i);
	}
}

int get(int i) {
	i++;
	int ret = 0;
	while (i) {
		ret += bit[i];
		i -= (i & -i);
	}
	return ret;
}

void dfs_sz(int u, int par) {
	sze[u] = 1;
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		dfs_sz(v, u);
		sze[u] += sz[v];
	}
}

int centroid(int u, int par, int mxsz) {
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		if (2*sze[v] > mxsz)return centroid(v, u, mxsz);
	}
	return u;
}

int findp(int u) {
	return pr[u] = (pr[u] == u ? u : findp(pr[u]));
}
 
void merge(int u, int v) {
	u = findp(u), v = findp(v);
	if (u == v)return;
	if (sz[u] < sz[v])swap(u, v);
	sz[u] += sz[v];
	pr[v] = u;
}
 
void init(int u, int par) {
	for (auto &[v, t] : adj[u]) {
		if (v == par)continue;
		p[v][0] = u;
		dep[v] = dep[u]+1;
		vt[v] = t;
		mn[v] = (vt[v] < vt[u] ? mn[u] : u);
		mx[v] = (vt[v] > vt[u] ? mx[u] : u);
		for (int i = 1; i < 17; i++) {
			p[v][i] = p[p[v][i-1]][i-1];
		}
		init(v, u);
	}
}
 
int lift(int u, int k) {
	for (int i = 0; i < 17; i++) {
		if ((k & (1 << i)))u = p[u][i];
	}
	return u;
}
 
int lca(int u, int v) {
	if (dep[u] < dep[v])swap(u, v);
	u = lift(u, dep[u]-dep[v]);
	if (u == v)return u;
	for (int i = 16; i >= 0; i--) {
		if (p[u][i] != p[v][i]) {
			u = p[u][i];
			v = p[v][i];
		}
	}
	return p[u][0];
}
 
bool sol(int u, int v) {
	if (findp(u) != findp(v))return false;
	int l = lca(u, v);
	if (dep[mx[u]] > dep[l])return false;
	if (dep[mn[v]] > dep[l])return false;
	if (l == v || l == u)return true;
	u = lift(u, dep[u]-dep[l]-1);
	v = lift(v, dep[v]-dep[l]-1);
	return (vt[v] < vt[u]);
}
int vv;
void dfs(int u, int par, int ls) {
	for (auto &t : c[u]) {
		ans[t] += get(t) + (vv <= t);
	}
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		if (t > ls)continue;
		dfs(v, u, t);
	}
}

void dfs2(int u, int par, int ls) {
	upd(ls, 1);
	ar.pb(ls);
	for (auto &[v, t] : adj[u]) {
		if (r[v] || v == par)continue;
		if (t < ls)continue;
		dfs2(v, u, t);
	}
}

void cen(int u) {
	dfs_sz(u, u);
	u = centroid(u, u, sze[u]);
	for (auto &[v, t] : adj[u]) {
		if (r[v])continue;
		vv = t;
		dfs(v, u, t);
		dfs2(v, u, t);
	}
	for (auto &t : c[u]) {
		ans[t] += get(t);
	}
	for (auto &x : ar)upd(x, -1);
  	ar.clear();
	r[u] = true;
	for (auto &[v, t] : adj[u]) {
		if (r[v])continue;
		cen(v);
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		pr[i] = i, sz[i] = 1;
	}
	q += n-1;
	bool ff = true;
	for (int i = 0; i < q; i++) {
		char ch;
		cin >> ch;
		if (ch == 'S') {
			int u, v;
			cin >> u >> v;
			--u, --v;
			qr.pb({0, u, v});
			adj[u].pb({v, i});
			adj[v].pb({u, i});
		} else if (ch == 'Q') {
			int u, v;
			cin >> u >> v;
			--u, --v;
			qr.pb({1, u, v});
		} else {
			ff = false;
			int u;
			cin >> u;
			--u;
			c[u].pb(i);
			qr.pb({2, u, i});
		}
	}
	vt[0] = q+5;
	init(0, 0);
	if (!ff) {
		for (int i = 0; i < n; i++)reverse(all(adj[i]));
		cen(0);
	}
	for (auto &[op, u, v] : qr) {
		if (!op) {
			merge(u, v);
		}
		else if (op == 1) {
			cout << (sol(u, v) ? "yes\n" : "no\n");
		} else {
			cout << ans[v] + 1 << "\n";
		}
	}
}

Compilation message

servers.cpp:3:37: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("Ofast, O2, O3")
      |                                     ^
servers.cpp:3:37: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
servers.cpp:19:24: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   19 | void upd(int i, int val) {
      |                        ^
servers.cpp:19:24: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:27:14: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   27 | int get(int i) {
      |              ^
servers.cpp:27:14: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:37:27: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   37 | void dfs_sz(int u, int par) {
      |                           ^
servers.cpp:37:27: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:46:38: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   46 | int centroid(int u, int par, int mxsz) {
      |                                      ^
servers.cpp:46:38: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:54:16: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   54 | int findp(int u) {
      |                ^
servers.cpp:54:16: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:58:24: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   58 | void merge(int u, int v) {
      |                        ^
servers.cpp:58:24: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:66:25: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   66 | void init(int u, int par) {
      |                         ^
servers.cpp:66:25: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:81:22: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   81 | int lift(int u, int k) {
      |                      ^
servers.cpp:81:22: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:88:21: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   88 | int lca(int u, int v) {
      |                     ^
servers.cpp:88:21: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:101:22: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  101 | bool sol(int u, int v) {
      |                      ^
servers.cpp:101:22: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:112:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  112 | void dfs(int u, int par, int ls) {
      |                                ^
servers.cpp:112:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:123:33: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  123 | void dfs2(int u, int par, int ls) {
      |                                 ^
servers.cpp:123:33: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:133:15: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  133 | void cen(int u) {
      |               ^
servers.cpp:133:15: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
servers.cpp:154:11: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  154 | int main () {
      |           ^
servers.cpp:154:11: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15088 KB Output is correct
2 Correct 23 ms 14804 KB Output is correct
3 Correct 30 ms 14848 KB Output is correct
4 Correct 34 ms 15028 KB Output is correct
5 Correct 33 ms 15268 KB Output is correct
6 Correct 33 ms 14836 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15088 KB Output is correct
2 Correct 23 ms 14804 KB Output is correct
3 Correct 30 ms 14848 KB Output is correct
4 Correct 34 ms 15028 KB Output is correct
5 Correct 33 ms 15268 KB Output is correct
6 Correct 33 ms 14836 KB Output is correct
7 Correct 24 ms 14804 KB Output is correct
8 Correct 44 ms 15276 KB Output is correct
9 Correct 39 ms 15460 KB Output is correct
10 Correct 142 ms 15372 KB Output is correct
11 Correct 134 ms 15620 KB Output is correct
12 Correct 39 ms 15336 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14688 KB Output is correct
2 Correct 123 ms 27436 KB Output is correct
3 Correct 97 ms 27144 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14688 KB Output is correct
2 Correct 123 ms 27436 KB Output is correct
3 Correct 97 ms 27144 KB Output is correct
4 Correct 24 ms 14760 KB Output is correct
5 Correct 142 ms 28312 KB Output is correct
6 Correct 97 ms 28816 KB Output is correct
7 Correct 110 ms 28912 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14676 KB Output is correct
2 Correct 120 ms 35624 KB Output is correct
3 Correct 115 ms 35604 KB Output is correct
4 Correct 104 ms 35556 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14676 KB Output is correct
2 Correct 120 ms 35624 KB Output is correct
3 Correct 115 ms 35604 KB Output is correct
4 Correct 104 ms 35556 KB Output is correct
5 Correct 18 ms 14672 KB Output is correct
6 Execution timed out 3547 ms 36596 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14700 KB Output is correct
2 Correct 86 ms 27208 KB Output is correct
3 Correct 124 ms 27688 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14700 KB Output is correct
2 Correct 86 ms 27208 KB Output is correct
3 Correct 124 ms 27688 KB Output is correct
4 Correct 22 ms 14820 KB Output is correct
5 Execution timed out 3591 ms 28648 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14800 KB Output is correct
2 Correct 111 ms 35756 KB Output is correct
3 Correct 101 ms 35604 KB Output is correct
4 Correct 86 ms 35696 KB Output is correct
5 Correct 19 ms 14808 KB Output is correct
6 Correct 84 ms 27144 KB Output is correct
7 Correct 101 ms 27580 KB Output is correct
8 Correct 114 ms 28108 KB Output is correct
9 Correct 123 ms 28136 KB Output is correct
10 Correct 119 ms 32608 KB Output is correct
11 Correct 123 ms 32020 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14800 KB Output is correct
2 Correct 111 ms 35756 KB Output is correct
3 Correct 101 ms 35604 KB Output is correct
4 Correct 86 ms 35696 KB Output is correct
5 Correct 19 ms 14808 KB Output is correct
6 Correct 84 ms 27144 KB Output is correct
7 Correct 101 ms 27580 KB Output is correct
8 Correct 114 ms 28108 KB Output is correct
9 Correct 123 ms 28136 KB Output is correct
10 Correct 119 ms 32608 KB Output is correct
11 Correct 123 ms 32020 KB Output is correct
12 Correct 20 ms 14628 KB Output is correct
13 Execution timed out 3540 ms 36864 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14800 KB Output is correct
2 Correct 22 ms 14812 KB Output is correct
3 Correct 30 ms 14980 KB Output is correct
4 Correct 22 ms 14856 KB Output is correct
5 Correct 32 ms 15112 KB Output is correct
6 Correct 33 ms 14964 KB Output is correct
7 Correct 34 ms 14644 KB Output is correct
8 Correct 92 ms 27124 KB Output is correct
9 Correct 91 ms 27132 KB Output is correct
10 Correct 20 ms 14716 KB Output is correct
11 Correct 100 ms 35584 KB Output is correct
12 Correct 114 ms 35616 KB Output is correct
13 Correct 83 ms 35832 KB Output is correct
14 Correct 19 ms 14760 KB Output is correct
15 Correct 80 ms 27208 KB Output is correct
16 Correct 109 ms 27732 KB Output is correct
17 Correct 135 ms 28376 KB Output is correct
18 Correct 119 ms 28104 KB Output is correct
19 Correct 113 ms 32596 KB Output is correct
20 Correct 174 ms 31920 KB Output is correct
21 Correct 89 ms 27136 KB Output is correct
22 Correct 88 ms 27160 KB Output is correct
23 Correct 102 ms 27524 KB Output is correct
24 Correct 111 ms 27728 KB Output is correct
25 Correct 108 ms 29396 KB Output is correct
26 Correct 105 ms 27180 KB Output is correct
27 Correct 80 ms 26908 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14800 KB Output is correct
2 Correct 22 ms 14812 KB Output is correct
3 Correct 30 ms 14980 KB Output is correct
4 Correct 22 ms 14856 KB Output is correct
5 Correct 32 ms 15112 KB Output is correct
6 Correct 33 ms 14964 KB Output is correct
7 Correct 34 ms 14644 KB Output is correct
8 Correct 92 ms 27124 KB Output is correct
9 Correct 91 ms 27132 KB Output is correct
10 Correct 20 ms 14716 KB Output is correct
11 Correct 100 ms 35584 KB Output is correct
12 Correct 114 ms 35616 KB Output is correct
13 Correct 83 ms 35832 KB Output is correct
14 Correct 19 ms 14760 KB Output is correct
15 Correct 80 ms 27208 KB Output is correct
16 Correct 109 ms 27732 KB Output is correct
17 Correct 135 ms 28376 KB Output is correct
18 Correct 119 ms 28104 KB Output is correct
19 Correct 113 ms 32596 KB Output is correct
20 Correct 174 ms 31920 KB Output is correct
21 Correct 89 ms 27136 KB Output is correct
22 Correct 88 ms 27160 KB Output is correct
23 Correct 102 ms 27524 KB Output is correct
24 Correct 111 ms 27728 KB Output is correct
25 Correct 108 ms 29396 KB Output is correct
26 Correct 105 ms 27180 KB Output is correct
27 Correct 80 ms 26908 KB Output is correct
28 Correct 19 ms 14804 KB Output is correct
29 Correct 42 ms 15360 KB Output is correct
30 Correct 30 ms 15288 KB Output is correct
31 Correct 132 ms 15376 KB Output is correct
32 Correct 133 ms 15616 KB Output is correct
33 Correct 29 ms 15324 KB Output is correct
34 Correct 20 ms 14800 KB Output is correct
35 Correct 134 ms 28412 KB Output is correct
36 Correct 79 ms 29196 KB Output is correct
37 Correct 85 ms 28860 KB Output is correct
38 Correct 18 ms 14804 KB Output is correct
39 Execution timed out 3562 ms 36776 KB Time limit exceeded
40 Halted 0 ms 0 KB -