Submission #2872

#	Time	Username	Problem	Language	Result	Execution time	Memory
2872		ladown21	간선 파괴 (GA5_destroy)	C++98	25 / 100	2500 ms	3400 KiB

destroy

#include <stdio.h>
#include <algorithm>

struct Edge{int a,b,i;}G[130000],q[50010];
Edge inner(int a,int b, int i)
{Edge r={a,b,i};return r;}

int T[800],ans[50010];

int ufind(int k)
{return T[k]=(T[k]==k)?k:ufind(T[k]);}

bool cmp_a(Edge a, Edge b)
{return ((a.a==b.a)?a.b>b.b:a.a<b.a);}
bool cmp_i(Edge a, Edge b)
{return a.i<b.i;}

int Cnt(int V)
{
	int C[800]={0}, ret=0;
	for (int i=1; i<=V; i++)
		ret += (C[T[i]]++)==0;
	return ret;
}

int main()
{
	int V,E,Q;
	scanf("%d%d",&V,&E);

	int u,v;
	for (int i=1; i<=E; i++) {
		scanf("%d%d",&u,&v);
		if (u>v) u^=v,v^=u,u^=v;
		G[i] = inner(u,v,i);
	}

	scanf("%d",&Q);
	for (int i=1; i<=Q; i++) {
		scanf("%d%d",&u,&v);
		q[i] = inner(u,v,i);
	}
	std::sort(q+1,q+1+Q, cmp_a);

	
	int a=0,b=E;
	for (int i=1; i<=Q; i++) {
		if (a!=q[i].a) {
			for (int i=1; i<=V; i++) T[i] = i;
			a=0;
			b=E;
		}

		for (int k=1; k<q[i].a; k++)
			T[ufind(G[k].a)] = ufind(G[k].b);
		for (int k=b; k>q[i].b; k--)
			T[ufind(G[k].a)] = ufind(G[k].b);
		for (int k=1; k<=V; k++) ufind(k);

		ans[q[i].i] = Cnt(V);
		a=q[i].a;
		b=q[i].b;
	}
	for (int i=1; i<=Q; i++)
		printf("%d\n",ans[i]);
}

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