oj.uz

Submission #655050

# Submission time Handle Problem Language Result Execution time Memory
655050 2022-11-02T21:20:29 Z GusterGoose27 Inside information (BOI21_servers) C++11
50 / 100
 262 ms 63308 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
const int inf = 1e9;

class Query {
public:
	bool type; // 0 = query, 1 = count
	int x, y, time;
	Query(bool t, int time, int x, int y=-1) : type(t), time(time), x(x), y(y) {}
	Query() {}
};

const int MAXN = 12e4;
const int MX_jump = 17;
vector<pii> edges[MAXN]; // node, time
pii lca[MAXN][MX_jump];
pii lca_rev[MAXN][MX_jump];
int lca_node[MAXN][MX_jump];
pii edge_list[MAXN];
Query queries[MAXN];
int depth[MAXN];

int n, q, t = 0, p = 0;

void dfs_lca(int cur = 0, int p = -1) {
	for (pii e: edges[cur]) {
		if (e.first == p) continue;
		depth[e.first] = 1+depth[cur];
		dfs_lca(e.first, cur);
		lca_node[e.first][0] = cur;
		lca[e.first][0] = pii(e.second, e.second);
		lca_rev[e.first][0] = pii(e.second, e.second);
	}
}

pii combine(pii a, pii b) {
	if (b.first <= a.second) return pii(-1, inf);
	return pii(a.first, b.second);
}

void make_lca() {
	for (int i = 1; i < MX_jump; i++) {
		for (int j = 0; j < n; j++) {
			lca_node[j][i] = lca_node[lca_node[j][i-1]][i-1];
			lca[j][i] = combine(lca[j][i-1], lca[lca_node[j][i-1]][i-1]);
			lca_rev[j][i] = combine(lca_rev[lca_node[j][i-1]][i-1], lca_rev[j][i-1]);
		}
	}
}

bool is_path(int a, int b, int t) {
	pii a_path = pii(-1, -1);
	pii b_path = pii(t, t);
	int d = depth[a]-depth[b];
	int pow = 0;
	while (d > 0) {
		if (d & 1) {
			a_path = combine(a_path, lca[a][pow]);
			a = lca_node[a][pow];
		}
		pow++;
		d /= 2;
	}
	d = depth[b]-depth[a];
	pow = 0;
	while (d > 0) {
		if (d & 1) {
			b_path = combine(lca_rev[b][pow], b_path);
			b = lca_node[b][pow];
		}
		pow++;
		d /= 2;
	}
	for (int i = MX_jump-1; i >= 0; i--) {
		if (lca_node[a][i] != lca_node[b][i]) {
			a_path = combine(a_path, lca[a][i]);
			b_path = combine(lca_rev[b][i], b_path);
			a = lca_node[a][i];
			b = lca_node[b][i];
		}
	}
	if (a != b) {
		a_path = combine(a_path, lca[a][0]);
		b_path = combine(lca_rev[b][0], b_path);
	}
	return (a_path.second < b_path.first);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	for (int i = 0; i < n+q-1; i++) {
		int a, b;
		char c; cin >> c >> a;
		a--;
		if (c == 'S') {
			cin >> b; b--;
			edge_list[t] = pii(a, b);
			edges[a].push_back(pii(b, t));
			edges[b].push_back(pii(a, t));
			t++;
		}
		else if (c == 'Q') {
			cin >> b; b--;
			queries[p++] = Query(0, i-p, a, b);
		}
		else queries[p++] = Query(1, i-p, a);
	}
	dfs_lca();
	make_lca();
	for (int i = 0; i < q; i++) {
		if (queries[i].type) {
			cout << "0\n";
		}
		else {
			if (is_path(queries[i].y, queries[i].x, queries[i].time)) cout << "yes\n";
			else cout << "no\n";
		}
	}
}

Compilation message

servers.cpp: In constructor 'Query::Query(bool, int, int, int)':
servers.cpp:11:12: warning: 'Query::time' will be initialized after [-Wreorder]
   11 |  int x, y, time;
      |            ^~~~
servers.cpp:11:6: warning:   'int Query::x' [-Wreorder]
   11 |  int x, y, time;
      |      ^
servers.cpp:12:2: warning:   when initialized here [-Wreorder]
   12 |  Query(bool t, int time, int x, int y=-1) : type(t), time(time), x(x), y(y) {}
      |  ^~~~~
servers.cpp: In function 'int main()':
servers.cpp:108:13: warning: operation on 'p' may be undefined [-Wsequence-point]
  108 |    queries[p++] = Query(0, i-p, a, b);
      |            ~^~
servers.cpp:108:13: warning: operation on 'p' may be undefined [-Wsequence-point]
servers.cpp:110:17: warning: operation on 'p' may be undefined [-Wsequence-point]
  110 |   else queries[p++] = Query(1, i-p, a);
      |                ~^~
servers.cpp:110:17: warning: operation on 'p' may be undefined [-Wsequence-point]

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6216 KB Output is correct
2 Correct 34 ms 8268 KB Output is correct
3 Correct 30 ms 8380 KB Output is correct
4 Correct 42 ms 8368 KB Output is correct
5 Correct 39 ms 8572 KB Output is correct
6 Correct 31 ms 8320 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6216 KB Output is correct
2 Correct 34 ms 8268 KB Output is correct
3 Correct 30 ms 8380 KB Output is correct
4 Correct 42 ms 8368 KB Output is correct
5 Correct 39 ms 8572 KB Output is correct
6 Correct 31 ms 8320 KB Output is correct
7 Incorrect 28 ms 6220 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 24 ms 6220 KB Output is correct
2 Correct 144 ms 54268 KB Output is correct
3 Correct 146 ms 54268 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6220 KB Output is correct
2 Correct 144 ms 54268 KB Output is correct
3 Correct 146 ms 54268 KB Output is correct
4 Incorrect 22 ms 6220 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 26 ms 6320 KB Output is correct
2 Correct 153 ms 63180 KB Output is correct
3 Correct 167 ms 63308 KB Output is correct
4 Correct 190 ms 63080 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6320 KB Output is correct
2 Correct 153 ms 63180 KB Output is correct
3 Correct 167 ms 63308 KB Output is correct
4 Correct 190 ms 63080 KB Output is correct
5 Incorrect 27 ms 6216 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 24 ms 6224 KB Output is correct
2 Correct 152 ms 54676 KB Output is correct
3 Correct 156 ms 55088 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6224 KB Output is correct
2 Correct 152 ms 54676 KB Output is correct
3 Correct 156 ms 55088 KB Output is correct
4 Incorrect 26 ms 6216 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 26 ms 6300 KB Output is correct
2 Correct 161 ms 63204 KB Output is correct
3 Correct 156 ms 63184 KB Output is correct
4 Correct 166 ms 63092 KB Output is correct
5 Correct 26 ms 6264 KB Output is correct
6 Correct 146 ms 54780 KB Output is correct
7 Correct 160 ms 55192 KB Output is correct
8 Correct 197 ms 55564 KB Output is correct
9 Correct 176 ms 55500 KB Output is correct
10 Correct 215 ms 60116 KB Output is correct
11 Correct 249 ms 59376 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6300 KB Output is correct
2 Correct 161 ms 63204 KB Output is correct
3 Correct 156 ms 63184 KB Output is correct
4 Correct 166 ms 63092 KB Output is correct
5 Correct 26 ms 6264 KB Output is correct
6 Correct 146 ms 54780 KB Output is correct
7 Correct 160 ms 55192 KB Output is correct
8 Correct 197 ms 55564 KB Output is correct
9 Correct 176 ms 55500 KB Output is correct
10 Correct 215 ms 60116 KB Output is correct
11 Correct 249 ms 59376 KB Output is correct
12 Incorrect 26 ms 6204 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 26 ms 6236 KB Output is correct
2 Correct 36 ms 8276 KB Output is correct
3 Correct 36 ms 8368 KB Output is correct
4 Correct 44 ms 8424 KB Output is correct
5 Correct 40 ms 8504 KB Output is correct
6 Correct 31 ms 8284 KB Output is correct
7 Correct 26 ms 6252 KB Output is correct
8 Correct 162 ms 54272 KB Output is correct
9 Correct 160 ms 54244 KB Output is correct
10 Correct 29 ms 6264 KB Output is correct
11 Correct 171 ms 63204 KB Output is correct
12 Correct 177 ms 63228 KB Output is correct
13 Correct 186 ms 63052 KB Output is correct
14 Correct 25 ms 6264 KB Output is correct
15 Correct 150 ms 54664 KB Output is correct
16 Correct 180 ms 55088 KB Output is correct
17 Correct 201 ms 55688 KB Output is correct
18 Correct 179 ms 55560 KB Output is correct
19 Correct 233 ms 60040 KB Output is correct
20 Correct 262 ms 59404 KB Output is correct
21 Correct 177 ms 54740 KB Output is correct
22 Correct 162 ms 54800 KB Output is correct
23 Correct 176 ms 55108 KB Output is correct
24 Correct 163 ms 55228 KB Output is correct
25 Correct 193 ms 56928 KB Output is correct
26 Correct 166 ms 54676 KB Output is correct
27 Correct 197 ms 54616 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6236 KB Output is correct
2 Correct 36 ms 8276 KB Output is correct
3 Correct 36 ms 8368 KB Output is correct
4 Correct 44 ms 8424 KB Output is correct
5 Correct 40 ms 8504 KB Output is correct
6 Correct 31 ms 8284 KB Output is correct
7 Correct 26 ms 6252 KB Output is correct
8 Correct 162 ms 54272 KB Output is correct
9 Correct 160 ms 54244 KB Output is correct
10 Correct 29 ms 6264 KB Output is correct
11 Correct 171 ms 63204 KB Output is correct
12 Correct 177 ms 63228 KB Output is correct
13 Correct 186 ms 63052 KB Output is correct
14 Correct 25 ms 6264 KB Output is correct
15 Correct 150 ms 54664 KB Output is correct
16 Correct 180 ms 55088 KB Output is correct
17 Correct 201 ms 55688 KB Output is correct
18 Correct 179 ms 55560 KB Output is correct
19 Correct 233 ms 60040 KB Output is correct
20 Correct 262 ms 59404 KB Output is correct
21 Correct 177 ms 54740 KB Output is correct
22 Correct 162 ms 54800 KB Output is correct
23 Correct 176 ms 55108 KB Output is correct
24 Correct 163 ms 55228 KB Output is correct
25 Correct 193 ms 56928 KB Output is correct
26 Correct 166 ms 54676 KB Output is correct
27 Correct 197 ms 54616 KB Output is correct
28 Incorrect 26 ms 6272 KB Extra information in the output file
29 Halted 0 ms 0 KB -