Submission #2870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2870	2013-08-01T05:37:26 Z	ladown21	간선 파괴 (GA5_destroy)	C++	25 / 100	2500 ms	2912 KB

destroy

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

using namespace std;

const int MAX_E = 130000;
const int MAX_V = 800;

struct Edge{int a,b;}edge[MAX_E];
Edge inner(int a,int b)
{Edge r={a,b};return r;}

int Component(int l,int r, int V, int E)
{
	vector<int> G[MAX_V];
	for (int k=1; k<=E; k++) {
		if (l==k) {k=r; continue;}
		G[edge[k].a].push_back(edge[k].b);
		G[edge[k].b].push_back(edge[k].a);
	}

	int M[MAX_V] = {0}, ret=0;
	for (int k=1; k<=V; k++) {
		if (M[k]) continue;
		
		queue<int> q;
		q.push(k);	M[k] = 1;
		while (!q.empty())
		{
			int x=q.front(); q.pop();
			int size=G[x].size();
			for (int i=0; i<size; i++) {
				int y=G[x][i];
				if (M[y]) continue;
				M[y] = 1;
				q.push(y);
			}
		}
		ret++;
	}
	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);
		edge[i] = inner(u,v);
	}
	scanf("%d",&Q);
	while (Q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",Component(l,r,V,E));
	}
}

Subtask #1

25.0 / 25.0

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

Subtask #2

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	884 ms	2384 KB	Output is correct
2	Correct	832 ms	2384 KB	Output is correct
3	Correct	932 ms	2384 KB	Output is correct
4	Correct	1860 ms	2780 KB	Output is correct
5	Correct	1712 ms	2780 KB	Output is correct
6	Runtime error	2464 ms	2780 KB	SIGKILL Killed
7	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 40.0

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