제출 #2998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2998		cki86201	간선 파괴 (GA5_destroy)	C++98	100 / 100	1764 ms	5728 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;

//slow O(QV) method;

const int ME = 250000;
const int MV = 710;
const int INF = 0x7fffffff;
int st[MV], en[ME], next[ME], sen[ME];
int nst[MV], nen[4*MV], nnext[4*MV],num[4*MV];
int E,V;
int MST[MV][2];	//0:minimum, 1:maximum;
int L[2];
int Q;
int chk[MV];
bool check[MV];
struct edge{
	edge(){}
	edge(int en,int len):en(en),len(len){}
	int en,len;
	bool operator>(const edge &l)const{
		return len>l.len;
	}
};
priority_queue <edge, vector<edge>, greater<edge> > heap;

void addedge(int s,int d,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
	sen[c]=s;
}

void naddedge(int s,int d,int c)
{
	nnext[c]=nst[s];
	nst[s]=c;
	nen[c]=d;
}

void find_MST(int x)
{
	memset(check,0,sizeof(check));
	int t=x?-1:1;
	int ct=0;
	while(!heap.empty())heap.pop();
	int u;
	for(u=1;u<=V;u++){
		if(check[u])continue;
		heap.push(edge(u,INF));
		while(!heap.empty() && ct!=V){
			edge tx = heap.top();
			heap.pop();
			if(check[tx.en])continue;
			check[tx.en]=1;
			if(tx.len!=INF)MST[++L[x]][x]=tx.len*t;
			int i;
			for(i=st[tx.en];i;i=next[i]){
				int ttx = en[i];
				if(check[ttx])continue;
				heap.push(edge(en[i],i/2*t));
			}
			ct++;
		}
	}
	for(int i=1;i<=L[x];i++){
		int c=i;
		if(x)c+=L[0];
		int mx = MST[i][x]*2;
		naddedge(sen[mx],en[mx],2*c);
		num[2*c]=mx/2;
		naddedge(en[mx],sen[mx],2*c+1);
		num[2*c+1]=mx/2;
	}
}

void dfs(int x,int s,int d)
{
	chk[x]=Q+1;
	int i;
	for(i=nst[x];i;i=nnext[i]){
		if(chk[nen[i]]==Q+1)continue;
		if(num[i]>=s&&num[i]<=d)continue;
		dfs(nen[i],s,d);
	}
}

void solve(int s,int d)
{
	int i,ans=0;
	for(i=1;i<=V;i++){
		if(chk[i]==Q+1)continue;
		dfs(i,s,d);
		ans++;
	}
	printf("%d\n",ans);
}

int main()
{
	scanf("%d%d",&V,&E);
	int i;
	for(i=1;i<=E;i++){
		int x,y;scanf("%d%d",&x,&y);
		addedge(x,y,2*i);
		addedge(y,x,2*i+1);
	}
	find_MST(0);
	find_MST(1);
	scanf("%d",&Q);
	while(Q--){
		int x,y;scanf("%d%d",&x,&y);
		solve(x,y);
	}
	return 0;
}

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