제출 #3004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3004		cki86201	간선 파괴 (GA5_destroy)	C++98	100 / 100	84 ms	6972 KiB

destroy

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<functional>
using namespace std;

// O(Q+V^2) method;

const int ME = 250000;
const int MV = 710;
const int INF = 0x7fffffff;
int A[ME],B[ME];
int p[MV],Rank[MV];
int E,V;
int D[MV][MV];
int tox[MV],toy[MV],lx,ly;
int ix[ME],iy[ME];

void init(){for(int i=1;i<=V;i++)p[i]=i,Rank[i]=1;}

int Find(int x)
{
	int a=x;
	while(p[x]!=x)x=p[x];
	while(a!=x){a=p[a];p[a]=x;}
	return x;
}

bool Union(int x,int y)
{
	x=Find(x), y=Find(y);
	if(Rank[x]>Rank[y])p[y]=p[x],Rank[x]+=Rank[y],Rank[y]=0;
	else p[x]=p[y],Rank[y]+=Rank[x],Rank[x]=0;
	return x==y;
}

int main()
{
	scanf("%d%d",&V,&E);
	int i,j;
	for(i=1;i<=E;i++)scanf("%d%d",A+i,B+i);
	init();
	for(i=1;i<=E;i++){
		if(!Union(A[i],B[i]))tox[++lx]=i;
	}
	init();
	for(i=E;i;i--){
		if(!Union(A[i],B[i]))toy[++ly]=i;
	}
	for(i=1;i<=lx+1;i++){
		int cnt=V;
		init();
		for(j=1;j<i;j++)if(!Union(A[tox[j]],B[tox[j]]))--cnt;
		for(j=1;j<=ly;j++){
			D[i][j]=cnt;
			if(!Union(A[toy[j]],B[toy[j]]))--cnt;
		}
		D[i][ly+1]=cnt;
	}
	for(i=1,j=1;i<=E;i++){
		ix[i]=j;
		if(tox[j]==i)j++;
	}
	for(i=E,j=1;i;i--){
		iy[i]=j;
		if(toy[j]==i)j++;
	}
	int q;scanf("%d",&q);
	while(q--){
		int x,y;scanf("%d%d",&x,&y);
		x=ix[x],y=iy[y];
		printf("%d\n",D[x][y]);
	}
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40