답안 #2694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2694	2013-07-30T15:28:01 Z	ainta	간선 파괴 (GA5_destroy)	C++	100 / 100	1944 ms	2060 KB

destroy

#include<stdio.h>
int n,m,b[700],e[700],Q,p[700],c;
struct Edge{
	int a,b;
}E[123457];
void init(){
	int i;
	for(i=1;i<=n;i++)p[i]=i;
}
int find(int a){
	if(a==p[a])return a;
	return p[a]=find(p[a]);
}
int main(){
	int i,j,x,y,R,bb,ee;
	scanf("%d%d",&n,&m);
	init();
	for(i=0;i<m;i++){
		scanf("%d%d",&E[i].a,&E[i].b);
		x=find(E[i].a),y=find(E[i].b);
		if(x!=y){
			p[x]=y;
			b[c++]=i;
		}
	}
	init();
	c=0;
	for(i=m-1;i>=0;i--){
		x=find(E[i].a),y=find(E[i].b);
		if(x!=y){
			p[x]=y;
			e[c++]=i;
		}
	}
	scanf("%d",&Q);
	while(Q--){
		scanf("%d%d",&bb,&ee);
		bb--,ee--;
		init();
		R=n;
		for(i=0;i<c;i++){
			if(b[i]>=bb)break;
			x=find(E[b[i]].a),y=find(E[b[i]].b);
			p[x]=y;
			R--;
		}
		for(i=0;i<c;i++){
			if(e[i]<=ee)break;
			x=find(E[e[i]].a),y=find(E[e[i]].b);
			if(x!=y)p[x]=y,R--;
		}
		printf("%d\n",R);
	}
}

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2060 KB	Output is correct
2	Correct	0 ms	2060 KB	Output is correct
3	Correct	0 ms	2060 KB	Output is correct
4	Correct	0 ms	2060 KB	Output is correct
5	Correct	0 ms	2060 KB	Output is correct
6	Correct	0 ms	2060 KB	Output is correct
7	Correct	0 ms	2060 KB	Output is correct
8	Correct	0 ms	2060 KB	Output is correct
9	Correct	0 ms	2060 KB	Output is correct
10	Correct	0 ms	2060 KB	Output is correct
11	Correct	0 ms	2060 KB	Output is correct
12	Correct	0 ms	2060 KB	Output is correct
13	Correct	0 ms	2060 KB	Output is correct
14	Correct	0 ms	2060 KB	Output is correct
15	Correct	0 ms	2060 KB	Output is correct
16	Correct	0 ms	2060 KB	Output is correct
17	Correct	0 ms	2060 KB	Output is correct
18	Correct	0 ms	2060 KB	Output is correct
19	Correct	0 ms	2060 KB	Output is correct
20	Correct	0 ms	2060 KB	Output is correct
21	Correct	0 ms	2060 KB	Output is correct
22	Correct	0 ms	2060 KB	Output is correct

Subtask #2

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	2060 KB	Output is correct
2	Correct	44 ms	2060 KB	Output is correct
3	Correct	44 ms	2060 KB	Output is correct
4	Correct	56 ms	2060 KB	Output is correct
5	Correct	52 ms	2060 KB	Output is correct
6	Correct	448 ms	2060 KB	Output is correct
7	Correct	484 ms	2060 KB	Output is correct
8	Correct	440 ms	2060 KB	Output is correct
9	Correct	44 ms	2060 KB	Output is correct
10	Correct	40 ms	2060 KB	Output is correct
11	Correct	40 ms	2060 KB	Output is correct
12	Correct	60 ms	2060 KB	Output is correct
13	Correct	56 ms	2060 KB	Output is correct
14	Correct	52 ms	2060 KB	Output is correct
15	Correct	36 ms	2060 KB	Output is correct
16	Correct	40 ms	2060 KB	Output is correct
17	Correct	12 ms	2060 KB	Output is correct
18	Correct	8 ms	2060 KB	Output is correct
19	Correct	4 ms	2060 KB	Output is correct
20	Correct	4 ms	2060 KB	Output is correct
21	Correct	0 ms	2060 KB	Output is correct
22	Correct	0 ms	2060 KB	Output is correct

Subtask #3

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1908 ms	2060 KB	Output is correct
2	Correct	1824 ms	2060 KB	Output is correct
3	Correct	1828 ms	2060 KB	Output is correct
4	Correct	1864 ms	2060 KB	Output is correct
5	Correct	1924 ms	2060 KB	Output is correct
6	Correct	1808 ms	2060 KB	Output is correct
7	Correct	1720 ms	2060 KB	Output is correct
8	Correct	1944 ms	2060 KB	Output is correct
9	Correct	1704 ms	2060 KB	Output is correct
10	Correct	1676 ms	2060 KB	Output is correct
11	Correct	1772 ms	2060 KB	Output is correct
12	Correct	1832 ms	2060 KB	Output is correct
13	Correct	1776 ms	2060 KB	Output is correct
14	Correct	1752 ms	2060 KB	Output is correct
15	Correct	1400 ms	2060 KB	Output is correct
16	Correct	1256 ms	2060 KB	Output is correct
17	Correct	516 ms	2060 KB	Output is correct
18	Correct	472 ms	2060 KB	Output is correct
19	Correct	116 ms	2060 KB	Output is correct
20	Correct	160 ms	2060 KB	Output is correct
21	Correct	32 ms	2060 KB	Output is correct
22	Correct	40 ms	2060 KB	Output is correct