【BZOJ1018】[SHOI2008]堵塞的交通

时间：2021-08-22 08:03:38

【BZOJ1018】[SHOI2008]堵塞的交通

题面

bzoj

洛谷

洛谷

题解

菊队讲要用线段树维护连通性，但是好像没人写

解法一

将所有的加边删边离线，然后以最近删除时间为边权，$LCT$维护最大生成树即可

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <map>

using namespace std;

inline int gi() {

	register int data = 0, w = 1;

	register char ch = 0;

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

	return w * data;

}

const int MAX_N = 100005;

const int INF = 1e9;

struct Node { int fa, ch[2], v, d; bool rev; } t[MAX_N << 2];

int stk[MAX_N << 2], top;

void pushup(int x) {

	t[x].d = x;

	if (t[t[x].d].v > t[t[t[x].ch[0]].d].v) t[x].d = t[t[x].ch[0]].d;

	if (t[t[x].d].v > t[t[t[x].ch[1]].d].v) t[x].d = t[t[x].ch[1]].d;

}

void pushrev(int x) {

	t[x].rev ^= 1;

	swap(t[x].ch[0], t[x].ch[1]);

}

void pushdown(int x) {

	if (!t[x].rev) return ;

	if (t[x].ch[0]) pushrev(t[x].ch[0]);

	if (t[x].ch[1]) pushrev(t[x].ch[1]);

	t[x].rev = 0;

}

int get(int x) { return t[t[x].fa].ch[1] == x; }

bool isroot(int x) { return (t[t[x].fa].ch[1] != x) && (t[t[x].fa].ch[0] != x); }

void rotate(int x) {

	int k = get(x), y = t[x].fa, z = t[y].fa;

	if (!isroot(y)) t[z].ch[get(y)] = x;

	t[x].fa = z;

	t[t[x].ch[k ^ 1]].fa = y, t[y].ch[k] = t[x].ch[k ^ 1];

	t[x].ch[k ^ 1] = y, t[y].fa = x;

	pushup(y), pushup(x);

}

void splay(int x) {

	stk[top = 1] = x;

	for (int i = x; !isroot(i); i = t[i].fa) stk[++top] = t[i].fa;

	for (int i = top; i; i--) pushdown(stk[i]);

	while (!isroot(x)) {

		int y = t[x].fa;

		if (!isroot(y)) (get(x) ^ get(y)) ? rotate(x) : rotate(y);

		rotate(x);

	}

}

void access(int x) { for (int y = 0; x; y = x, x = t[x].fa) splay(x), t[x].ch[1] = y, pushup(x); }

int findroot(int x) { access(x); splay(x); while (t[x].ch[0]) pushdown(x), x = t[x].ch[0]; return x; }

void makeroot(int x) { access(x); splay(x); pushrev(x); }

void split(int x, int y) { makeroot(x); access(y); splay(y); }

void link(int x, int y) { makeroot(x); t[x].fa = y; }

void cut(int x, int y) { split(x, y); t[y].ch[0] = t[x].fa = 0, pushup(y); }

int N, C, tot;

struct Opt { int t, op, x1, x2, del; } a[MAX_N << 1];

map<pair<int, int>, int> mp;

int main () {

#ifndef ONLINE_JUDGE

	freopen("cpp.in", "r", stdin);

	freopen("cpp.out", "w", stdout);

#endif

	C = gi();

    for ( ; ; )  {

		char ch[10]; scanf("%s", ch);

		if (ch[0] == 'E') break;

		int op, r1 = gi() - 1, c1 = gi(), r2 = gi() - 1, c2 = gi(), x1 = r1 * C + c1, x2 = r2 * C + c2;

		if (x1 > x2) swap(x1, x2);

		if (ch[0] == 'O') op = 0;

		if (ch[0] == 'C') op = 1;

		if (ch[0] == 'A') op = 2;

		++N;

		if (op == 0) mp[pair<int, int>(x1, x2)] = N, a[N].del = INF;

		if (op == 1) a[mp[pair<int, int>(x1, x2)]].del = N;

		a[N].t = N, a[N].op = op, a[N].x1 = x1, a[N].x2 = x2;

	}

	tot = 2 * C;

	for (int i = 0; i <= tot; i++) t[i].v = INF;

	for (int i = 1; i <= N; i++) {

		int x1 = a[i].x1, x2 = a[i].x2, del = a[i].del;

		if (a[i].op == 0) {

			if (findroot(x1) == findroot(x2)) {

				split(x1, x2); int d = t[x2].d;

				if (t[d].v >= del) continue;

				else cut(x1, d), cut(x2, d);

				t[++tot].v = del;

				link(x1, tot), link(x2, tot);

			}

			else t[++tot].v = del, link(x1, tot), link(x2, tot);

		}

	    if (a[i].op == 1)

			if (findroot(x1) == findroot(x2)) {

			    split(x1, x2);

				int d = t[x2].d;

				if (t[d].v > a[i].t) continue;

				cut(x1, d), cut(x2, d);

			}

		if (a[i].op == 2) {

			if (findroot(x1) == findroot(x2)) puts("Y");

			else puts("N");

		}

	}

	return 0;

}

解法二

没打，但是可以参考这篇文章

相关文章