oj.uz

Submission #655643

# Submission time Handle Problem Language Result Execution time Memory
655643 2022-11-05T04:46:36 Z GusterGoose27 Inside information (BOI21_servers) C++11
0 / 100
 30 ms 8340 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];
vector<int> cent_graph[MAXN];
int cent_par[MAXN];
bool vis[MAXN];
int sz[MAXN];
int rt;

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);
	} // confirmed
}

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

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]);
		}
	} // confirmed
}

pair<pii, pii> get_path(int a, int b) { // a != b
	pii a_path = pii(-1, -1);
	pii b_path = pii(inf, inf);
	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 pair<pii, pii>(a_path, b_path);
}

bool is_path(int a, int b, int t) {
	pair<pii, pii> v = get_path(a, b);
	return v.first.second < v.second.first && v.second.second < t;
}

int path_end(int a, int b) {
	pair<pii, pii> v = get_path(a, b);
	return combine(v.first, v.second).second;
}

void make_sz(int cur, int p = -1) {
	sz[cur] = 1;
	for (pii e: edges[cur]) {
		int nxt = e.first;
		if (nxt == p || vis[nxt]) continue;
		make_sz(nxt, cur);
		sz[cur] += sz[nxt];
	}
}

int cent_dec(int cur) {
	make_sz(cur);
	int tot = sz[cur];
	bool next_found = 1;
	int p = -1;
	while (next_found) {
		next_found = 0;
		for (pii e: edges[cur]) {
			int nxt = e.first;
			if (nxt == p || vis[nxt]) continue;
			if (sz[nxt] > tot/2) {
				p = cur;
				cur = nxt;
				next_found = 1;
				break;
			}
		}
	}
	vis[cur] = 1;
	for (pii e: edges[cur]) {
		if (!vis[e.first]) {
			int c = cent_dec(e.first);
			cent_graph[cur].push_back(c);
			cent_par[c] = cur;
		}
	}
	return cur;
}

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();
	rt = cent_dec(0);
	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:163:13: warning: operation on 'p' may be undefined [-Wsequence-point]
  163 |    queries[p++] = Query(0, i-p, a, b);
      |            ~^~
servers.cpp:163:13: warning: operation on 'p' may be undefined [-Wsequence-point]
servers.cpp:165:17: warning: operation on 'p' may be undefined [-Wsequence-point]
  165 |   else queries[p++] = Query(1, i-p, a);
      |                ~^~
servers.cpp:165:17: warning: operation on 'p' may be undefined [-Wsequence-point]

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 8220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 8220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 8216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 8216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 8340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 8340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 8244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 8244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 8252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 8252 KB Output isn't correct
2 Halted 0 ms 0 KB -