oj.uz

Submission #2871

# Submission time Handle Problem Language Result Execution time Memory
2871 2013-08-01T06:19:23 Z ladown21 간선 파괴 (GA5_destroy) C++
0 / 100
 2500 ms 3400 KB 
#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);

	
	for (int i=1; i<=V; i++) T[i] = i;

	int a=1,b=V;
	for (int i=1; i<=Q; i++) {
		for (int k=a; 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);

		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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 3400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2500 ms 3396 KB Program timed out
2 Halted 0 ms 0 KB -