bzoj 4025: 二分图
巷北
posted @ 2015年5月15日 13:32
in bzoj
, 878 阅读
对时间分治，用启发式并查集维护一下，时间复杂度O(mlog^2n)，然而并查集常数极小，所以跑的比lct的O(mlogn)还快。
lct见http://wuzuofan.is-programmer.com/posts/89928.html 或者 http://c-sunshine.logdown.com
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<ctime>#include<cmath>using namespace std;typedef pair<int, int> Pii;typedef long long LL;typedef long double db;#define rep(_,A,B) for(_=A;_<=B;++_)#define repi(_,A,B) for(register int _=A;_<=B;++_)#define FOR(_,A) for(int _=h[A];_;_=next[_])#define A first#define B second#define mp make_pairchar o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}const int L = 100005, M = 200005;int n, m, T;struct M{ int u, v, st, ed; } e[M];int fa[L], d[L], a[L], q[M], top; Pii findx(int x) { int t = 0; for(; fa[x] != x; x = fa[x]) t ^= a[x]; return mp(x, t);}void merge(int x, int y, int dep) { if(d[x] > d[y]) swap(x, y); if(d[x] == d[y]) ++d[y], q[++top] = -y; fa[x] = y, a[x] = dep, q[++top] = x;}void resume(int t) { for(; top != t; --top) if(q[top] > 0) fa[q[top]] = q[top], a[q[top]] = 0; else --d[-q[top]];}void init(void) { cin >> n >> m >> T; repi(i, 1, m) { read(e[i].u), read(e[i].v), read(e[i].st), read(e[i].ed), ++e[i].st; if(e[i].st > e[i].ed) --m, --i; } repi(i, 1, n) fa[i] = i, d[i] = 1;}void solve(int l, int r, int r0) { int now = top, mid = l + r >> 1, i, j; rep(i, 1, r0) if(e[i].st <= l && r <= e[i].ed) { Pii x = findx(e[i].u), y = findx(e[i].v); int fx = x.A, fy = y.A, dep = !(x.B ^ y.B); if(fx != fy) merge(fx, fy, dep); else if(dep){ while(l <= r) puts("No"), ++l; resume(now); return ; } swap(e[r0--], e[i--]); } if(l == r) { puts("Yes"); return ; } for(i = 1, j = r0; i <= j; ++i) if(e[i].st > mid) swap(e[i--], e[j--]); solve(l, mid, j); for(i = 1, j = r0; i <= j; ++i) if(e[i].ed <= mid) swap(e[i--], e[j--]); solve(mid + 1, r, j); resume(now);}void work(void) { solve(1, T, m); }int main(void) { freopen("4025.in","r",stdin), freopen("4025.out","w",stdout); init(), work(); return 0;} |
评论 (0)
