[AHOI 2013] 连通图

bzoj 3237

思路

线段树分治

将询问的标号作为时间,其他就都和上一题一样了

(因为懒得手写链表所以这个代码BZOJ会T)

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

struct Edge {int x, y;}a[200010];
int N, M, fa[100010], siz[100010], dep[100010], sf[4000010], sd[4000010], top, cnt;
std::vector<int>tim[200010];
std::vector<Edge>vec[400010];

void add(int p, int L, int R, int s, int t, Edge val){ 
	if(s>t) return;
	if(s<=L && R<=t) {vec[p].push_back(val); return;}
	if(2*s<=L+R) add(p<<1, L, (L+R)/2, s, t, val);
	if(2*t>L+R)  add(p<<1|1, (L+R)/2+1, R, s, t, val);
}

inline int find(int x) {while(fa[x]) x=fa[x]; return x;}

void merge(int x, int y){
	x=find(x); y=find(y);
	if(x==y) return; ++top; cnt--;
	if(dep[x]>dep[y]) std::swap(x, y);
	sf[top]=x; fa[x]=y;
	if(dep[x]==dep[y]) sd[top]=1, dep[y]++;
	else			   sd[top]=0;
}

void divide(int p, int L, int R){
	std::vector<Edge>::iterator it; int tmp=top;
	for(it=vec[p].begin(); it!=vec[p].end(); it++)
		merge(it->x, it->y);
	if(L==R) puts(cnt==1 ? "Connected" : "Disconnected");
	else     {divide(p<<1, L, (L+R)/2); divide(p<<1|1, (L+R)/2+1, R);}
	for(; top>tmp; top--) dep[fa[sf[top]]]-=sd[top], fa[sf[top]]=0, cnt++;
}

void input(int &_){
	char ch=getchar(); _=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') _=_*10+ch-'0', ch=getchar();
}

int main(){
	int K, C, x;
	input(N); input(M); cnt=N;
	for(int i=1; i<=N; i++) siz[i]=1;
	for(int i=1; i<=M; i++) {input(a[i].x); input(a[i].y);}
	input(K);
	for(int i=1; i<=K; i++){
		input(C);
		for(int j=1; j<=C; j++){
			scanf("%d", &x); tim[x].push_back(i);
		}
	}
	for(int i=1; i<=M; i++){
		tim[i].push_back(0); tim[i].push_back(K+1); 
		std::sort(tim[i].begin(), tim[i].end());
	}
	std::vector<int>::iterator it;
	for(int i=1; i<=M; i++)
		for(it=tim[i].begin()+1; it!=tim[i].end(); it++)
			add(1, 1, K, (*(it-1))+1, (*it)-1, a[i]);
	divide(1, 1, K);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注