Submission #698019

#	Time	Username	Problem	Language	Result	Execution time	Memory
698019		GusterGoose27	Jail (JOI22_jail)	C++17	100 / 100	893 ms	101460 KiB

jail

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 12e4;

vector<int> edges[MAXN];
vector<int> edges_expanded[5*MAXN]; // nodes for queries, tree nodes (2light), tree nodes (4heavy)
int in_deg[5*MAXN];
int N=0;
int r=0;
int n, m;
int sz[MAXN];
int depth[MAXN];
int to_hld[MAXN];
int par[MAXN];
vector<int> in_hld[MAXN]; // bottom to top
int light_ids[MAXN][2];
pii startend[MAXN];

void clear() {
	for (int i = 0; i < n; i++) {
		edges[i].clear();
		to_hld[i] = -1;
		in_hld[i].clear();
		startend[i] = pii(-1, -1);
	}
	for (int i = 0; i < N; i++) {
		edges_expanded[i].clear();
		in_deg[i] = 0;
	}
	N=0;
	r=0;
}

void make_edge(int a, int b) {
	// assert(a != 17 || b != 18);
	in_deg[b]++;
	edges_expanded[a].push_back(b);
}

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int id;
	stree(int lv, int rv, bool ud) { // 1 => down, 0 => up
		lp = lv;
		rp = rv;
		id = N++;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid, ud);
			r = new stree(mid+1, rp, ud);
			if (ud) {
				make_edge(id, l->id);
				make_edge(id, r->id);
			}
			else {
				make_edge(l->id, id);
				make_edge(r->id, id);
			}
		}
	}
	void connect(int lv, int rv, int i, bool ud) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			if (ud) make_edge(i, id);
			else make_edge(id, i);
			return;
		}
		l->connect(lv, rv, i, ud);
		r->connect(lv, rv, i, ud);
	}
};

stree *trees[MAXN][2];

void dfs(int cur = 0, int p = -1) {
	sz[cur] = 1;
	for (int nxt: edges[cur]) {
		if (nxt == p) continue;
		depth[nxt] = depth[cur]+1;
		par[nxt] = cur;
		dfs(nxt, cur);
		sz[cur] += sz[nxt];
	}
}

void make_hld(int cur = 0, int p = -1) {
	for (int nxt: edges[cur]) {
		if (nxt == p) continue;
		if (sz[nxt] > sz[cur]/2) {
			if (to_hld[cur] == -1) {
				to_hld[cur] = cur;
			}
			to_hld[nxt] = to_hld[cur];
			make_hld(nxt, cur);
		}
		else make_hld(nxt, cur);
	}
	if (to_hld[cur] != -1) in_hld[to_hld[cur]].push_back(cur);
	else {
		light_ids[cur][0] = N++;
		light_ids[cur][1] = N++;
	}
}

bool comp(int x, int y) {
	if (to_hld[x] == -1 && to_hld[y] == -1) return depth[x] < depth[y];
	if (to_hld[x] == -1) {
		return pii(depth[x], depth[x]) < pii(depth[to_hld[y]], depth[y]);
	}
	if (to_hld[y] == -1) {
		return pii(depth[y], depth[y]) > pii(depth[to_hld[x]], depth[x]);
	}
	return pii(depth[to_hld[x]], depth[x]) < pii(depth[to_hld[y]], depth[y]);
}

void make_path(int x, int y, bool excx, bool excy) {
	if (x == y) {
		if (excx || excy) return;
		if (to_hld[x] == -1) {
			make_edge(light_ids[x][0], N-1);
			make_edge(N-1, light_ids[x][1]);
			return;
		}
	}
	if (comp(x, y)) {
		swap(x, y);
		swap(excx, excy);
	}
	if (to_hld[x] != -1 && to_hld[x] == to_hld[y]) {
		int curhld = to_hld[x];
		int d1 = depth[in_hld[curhld][0]]-depth[x];
		int d2 = depth[in_hld[curhld][0]]-depth[y];
		if (excx) d1++;
		if (excy) d2--;
		trees[curhld][0]->connect(d1, d2, N-1, 0);
		trees[curhld][1]->connect(d1, d2, N-1, 1);
		return;
	}
	if (to_hld[x] == -1) {
		if (excx) {
			return make_path(par[x], y, 0, excy);
		}
		make_edge(light_ids[x][0], N-1);
		make_edge(N-1, light_ids[x][1]);
		return make_path(par[x], y, excx, excy);
	}
	int curhld = to_hld[x];
	int d1 = depth[in_hld[curhld][0]]-depth[x];
	int d2 = in_hld[curhld].size()-1;
	if (excx) {
		d1++;
		excx = 0;
	}
	trees[curhld][0]->connect(d1, d2, N-1, 0);
	trees[curhld][1]->connect(d1, d2, N-1, 1);
	return make_path(par[to_hld[x]], y, excx, excy);
}

void prune(int cur) {
	in_deg[cur] = -1;
	r++;
	// cout << cur << "\n";
	for (int nxt: edges_expanded[cur]) {
		in_deg[nxt]--;
		if (in_deg[nxt] == 0) prune(nxt);
	}
}

int main() {
	int t; cin >> t;
	fill(to_hld, to_hld+MAXN, -1);
	fill(startend, startend+MAXN, pii(-1, -1));
	while (t--) {
		cin >> n;
		for (int i = 0; i < n-1; i++) {
			int x, y; cin >> x >> y;
			x--; y--;
			edges[x].push_back(y);
			edges[y].push_back(x);
		}
		dfs();
		make_hld();
		for (int i = 0; i < n; i++) {
			if (to_hld[i] == i) {
				for (int j = 0; j < 2; j++) {
					trees[i][j] = new stree(0, in_hld[i].size()-1, j);
				}
			}
		}
		cin >> m;
		for (int i = 0; i < m; i++) {
			int x, y; cin >> x >> y;
			x--; y--;
			N++;
			startend[x].first = N-1;
			startend[y].second = N-1;
			if (to_hld[y] == -1) {
				make_edge(light_ids[y][1], N-1);
			}
			else {
				int curhld = to_hld[y];
				int d = -depth[y]+depth[in_hld[curhld][0]];
				trees[curhld][1]->connect(d, d, N-1, 0);
			}
			if (to_hld[x] == -1) {
				make_edge(N-1, light_ids[x][0]);
			}
			else {
				int curhld = to_hld[x];
				int d = -depth[x]+depth[in_hld[curhld][0]];
				trees[curhld][0]->connect(d, d, N-1, 1);
			}
			make_path(x, y, 1, 1);
		}
		for (int i = 0; i < n; i++) {
			if (startend[i].first != -1 && startend[i].second != -1) {
				make_edge(startend[i].first, startend[i].second);
			}
		}
		for (int i = 0; i < N; i++) {
			if (in_deg[i] == 0) prune(i);
		}
		if (r == N) {
			cout << "Yes\n";
		}
		else cout << "No\n";
		clear();
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23