oj.uz

답안 #3169

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3169 2013-08-27T08:59:51 Z myungwoo 간선 파괴 (GA5_destroy) C++
100 / 100
 2176 ms 3260 KB 
#include <stdio.h>

#define MAXN 707
#define MAXM 123460

int N,M,Q;
int mom[MAXN],prev[MAXM],next[MAXM];
bool fchk[MAXM],bchk[MAXM];

struct Edge{
	Edge(int a=0,int b=0): a(a), b(b) {}
	int a,b;
} edge[MAXM];

int _find(int n){ return mom[n]==n?n:(mom[n]=_find(mom[n])); }
int _union(int a,int b){ a = _find(a), b = _find(b); if (a != b){ mom[b] = a; return 1; } return 0; }

int main()
{
	int i,k,s,e;
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++) scanf("%d%d",&s,&e), edge[i] = Edge(s,e);
	for (i=1;i<=N;i++) mom[i] = i;
	for (i=1,k=0;i<=M;i++){
		prev[i] = k;
		if (_union(edge[i].a,edge[i].b)){
			fchk[i] = 1;
			k = i;
		}
	}
	for (i=1;i<=N;i++) mom[i] = i;
	for (i=M,k=M+1;i>0;i--){
		next[i] = k;
		if (_union(edge[i].a,edge[i].b)){
			bchk[i] = 1;
			k = i;
		}
	}
	for (scanf("%d",&Q);Q--;){
		scanf("%d%d",&s,&e);
		for (i=1;i<=N;i++) mom[i] = i;
		for (--s;s>0;s=prev[s]) if (fchk[s]){
			_union(edge[s].a,edge[s].b);
		}
		for (++e;e<=M;e=next[e]) if (bchk[e]){
			_union(edge[e].a,edge[e].b);
		}
		int ans=0;
		for (i=1;i<=N;i++) if (_find(i) == i){
			ans++;
		}
		printf("%d\n",ans);
	}
}

Subtask #1
25.0 / 25.0

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 3260 KB Output is correct
2 Correct 56 ms 3260 KB Output is correct
3 Correct 60 ms 3260 KB Output is correct
4 Correct 64 ms 3260 KB Output is correct
5 Correct 64 ms 3260 KB Output is correct
6 Correct 564 ms 3260 KB Output is correct
7 Correct 552 ms 3260 KB Output is correct
8 Correct 524 ms 3260 KB Output is correct
9 Correct 60 ms 3260 KB Output is correct
10 Correct 52 ms 3260 KB Output is correct
11 Correct 56 ms 3260 KB Output is correct
12 Correct 60 ms 3260 KB Output is correct
13 Correct 56 ms 3260 KB Output is correct
14 Correct 60 ms 3260 KB Output is correct
15 Correct 52 ms 3260 KB Output is correct
16 Correct 60 ms 3260 KB Output is correct
17 Correct 28 ms 3260 KB Output is correct
18 Correct 20 ms 3260 KB Output is correct
19 Correct 12 ms 3260 KB Output is correct
20 Correct 12 ms 3260 KB Output is correct
21 Correct 4 ms 3260 KB Output is correct
22 Correct 4 ms 3260 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2060 ms 3260 KB Output is correct
2 Correct 1888 ms 3260 KB Output is correct
3 Correct 2060 ms 3260 KB Output is correct
4 Correct 1980 ms 3260 KB Output is correct
5 Correct 2076 ms 3260 KB Output is correct
6 Correct 1968 ms 3260 KB Output is correct
7 Correct 2076 ms 3260 KB Output is correct
8 Correct 2132 ms 3260 KB Output is correct
9 Correct 2052 ms 3260 KB Output is correct
10 Correct 2176 ms 3260 KB Output is correct
11 Correct 1960 ms 3260 KB Output is correct
12 Correct 1984 ms 3260 KB Output is correct
13 Correct 1860 ms 3260 KB Output is correct
14 Correct 1948 ms 3260 KB Output is correct
15 Correct 1912 ms 3260 KB Output is correct
16 Correct 1780 ms 3260 KB Output is correct
17 Correct 1052 ms 3260 KB Output is correct
18 Correct 1020 ms 3260 KB Output is correct
19 Correct 408 ms 3260 KB Output is correct
20 Correct 532 ms 3260 KB Output is correct
21 Correct 176 ms 3260 KB Output is correct
22 Correct 188 ms 3260 KB Output is correct