Submission #656262

#	Time	Username	Problem	Language	Result	Execution time	Memory
656262		GusterGoose27	Inside information (BOI21_servers)	C++11	50 / 100	466 ms	101700 KiB

servers

#include <bits/stdc++.h>

using namespace std;

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

struct rev_comp {
	bool operator()(pii &a, pii &b) {
		return (a.second == b.second) ? (a.first < b.first) : (a.second < b.second);
	}
} rev_comp;

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

const int MAXN = 12e4;
const int MX_jump = 17;
vector<pii> edges[MAXN]; // node, ti
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;
vector<int> edge_weights[MAXN];
int qans[MAXN];

class stree { // point update the exact edge weight. query to the right
public:
	int sum = 0;
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	stree(int node, int lv, int rv) {
		lp = edge_weights[node][lv];
		rp = edge_weights[node][rv];
		if (lp < rp) {
			int mid = (lv+rv)/2;
			l = new stree(node, lv, mid);
			r = new stree(node, mid+1, rv);
		}
	}
	int query(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return sum;
		return l->query(lv, rv)+r->query(lv, rv);
	}
	void upd(int p, int v = 1) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			sum += v;
			return;
		}
		l->upd(p, v);
		r->upd(p, v);
		sum = l->sum+r->sum;
	}
};

stree *trees[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);
	} // confirmed
}

pii combine(pii a, pii b) {
	if (b == pii(-2, -2)) return a;
	if (a == pii(-2, -2)) return b;
	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
}

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

bool is_path(int a, int b, int t) {
	return get_path(a, b).second < t;
}

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;
	trees[cur] = new stree(cur, 0, edge_weights[cur].size()-1);
	trees[cur]->upd(inf);
	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 make_ans(int node, int par) {
	if (par == -1) return 0;
	return trees[par]->query(get_path(node, par).second+1, inf)+make_ans(node, cent_par[par]);
}

void update_node(int node, int par, int ti) {
	if (par == -1) return;
	pii p = get_path(par, node);
	if (p.second == ti) trees[par]->upd(p.first);
	update_node(node, cent_par[par], ti);
}

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));
			edge_weights[a].push_back(t);
			edge_weights[b].push_back(t);
			t++;
		}
		else if (c == 'Q') {
			cin >> b; b--;
			queries[p] = Query(0, i-p, a, b);
			p++;
		}
		else {
			queries[p] = Query(1, i-p, a);
			p++;
		}
	}
	for (int i = 0; i < n; i++) {
		sort(edge_weights[i].begin(), edge_weights[i].end());
		unique(edge_weights[i].begin(), edge_weights[i].end());
		edge_weights[i].push_back(inf);
	}
	dfs_lca();
	make_lca();
	rt = cent_dec(0);
	cent_par[rt] = -1;
	int i = 0;
	int j = 0;
	while (i < q) {
		if (!queries[i].type) {
			i++;
		}
		else if (queries[i].ti <= j) {
			qans[i] = make_ans(queries[i].x, queries[i].x);
			i++;
		}
		else {
			update_node(edge_list[j].first, edge_list[j].first, j);
			update_node(edge_list[j].second, edge_list[j].second, j);
			j++;
		}
	}
	for (int i = 0; i < q; i++) {
		if (queries[i].type) {
			cout << qans[i] << '\n';
		}
		else {
			if (is_path(queries[i].y, queries[i].x, queries[i].ti)) cout << "yes\n";
			else cout << "no\n";
		}
	}
}

Compilation message (stderr)

servers.cpp: In constructor 'Query::Query(bool, int, int, int)':
servers.cpp:17:12: warning: 'Query::ti' will be initialized after [-Wreorder]
   17 |  int x, y, ti;
      |            ^~
servers.cpp:17:6: warning:   'int Query::x' [-Wreorder]
   17 |  int x, y, ti;
      |      ^
servers.cpp:18:2: warning:   when initialized here [-Wreorder]
   18 |  Query(bool t, int ti, int x, int y=-1) : type(t), ti(ti), x(x), y(y) {}
      |  ^~~~~

• 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