Submission #2867

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2867	2013-08-01T04:56:53 Z	ladown21	간선 파괴 (GA5_destroy)	C++	25 / 100	2500 ms	1364 KB

destroy

#include <stdio.h>

struct Edge{int a,b;};
Edge inner(int a,int b)
{Edge r={a,b};return r;}

int ufind(int k, int *T)
{
	if (T[k] == k) return k;
	return T[k] = ufind(T[k], T);
}

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

	Edge G[50010];
	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);
	}

	scanf("%d",&Q);
	while (Q--)
	{
		int T[510]={0}, a,b;
		for (int i=1; i<=V; i++)
			T[i] = i;

		scanf("%d%d",&a,&b);
		for (int i=1; i<=E; i++) {
			if (a<=i && i<=b) continue;
			int x = ufind(G[i].a, T);
			int y = ufind(G[i].b, T);
			T[x] = y;
		}
		for (int i=1; i<=V; i++) 
			ufind(i,T);

		int C[510]={0}, ret=0;
		for (int i=1; i<=V; i++)
			ret += (C[T[i]]++)==0;
		printf("%d\n",ret);
	}
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1356 KB	Output is correct
2	Correct	0 ms	1364 KB	Output is correct
3	Correct	0 ms	1360 KB	Output is correct
4	Correct	0 ms	1356 KB	Output is correct
5	Correct	0 ms	1360 KB	Output is correct
6	Correct	0 ms	1364 KB	Output is correct
7	Correct	0 ms	1364 KB	Output is correct
8	Correct	0 ms	1360 KB	Output is correct
9	Correct	0 ms	1360 KB	Output is correct
10	Correct	0 ms	1360 KB	Output is correct
11	Correct	0 ms	1364 KB	Output is correct
12	Correct	0 ms	1356 KB	Output is correct
13	Correct	0 ms	1360 KB	Output is correct
14	Correct	0 ms	1360 KB	Output is correct
15	Correct	0 ms	1364 KB	Output is correct
16	Correct	0 ms	1364 KB	Output is correct
17	Correct	0 ms	1360 KB	Output is correct
18	Correct	0 ms	1364 KB	Output is correct
19	Correct	0 ms	1360 KB	Output is correct
20	Correct	0 ms	1360 KB	Output is correct
21	Correct	0 ms	1364 KB	Output is correct
22	Correct	0 ms	1356 KB	Output is correct

Subtask #2

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	364 ms	1356 KB	Output is correct
2	Correct	364 ms	1356 KB	Output is correct
3	Correct	400 ms	1356 KB	Output is correct
4	Correct	1088 ms	1356 KB	Output is correct
5	Correct	1120 ms	1360 KB	Output is correct
6	Execution timed out	2500 ms	1360 KB	Program timed out
7	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 40.0

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