Submission #655050

#	Time	Username	Problem	Language	Result	Execution time	Memory
655050		GusterGoose27	Inside information (BOI21_servers)	C++11	50 / 100	262 ms	63308 KiB

servers

#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 (stderr)

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5