oj.uz

답안 #2691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
2691 2013-07-30T15:23:39 Z tncks0121 간선 파괴 (GA5_destroy) C++
100 / 100
 1800 ms 1880 KB 
#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

const int N_ = 1005;
const int M_ = 200005;

int N, M, Q;
short A[M_], B[M_];

short parent[N_];
short rank[N_];

void init() { for(int i = 1; i <= N; i++) parent[i] = rank[i] = i; }

short get(short u) {
    int r = u;
    while(parent[r] != r) r = parent[r];
    while(u != r) {
        int p = parent[u];
        parent[u] = r;
        u = p;
    }
    return r;
}

bool merge (short a, short b) {
    a = get(a); b = get(b);
  if(rank[a] < rank[b]) {
    parent[a] = b;
  }else if(rank[a] > rank[b]) {
    parent[b] = a;
  }else {
    parent[b] = a;
    ++rank[a];
  }
    return a != b;
}

int R[N_*2], RN;

int main () {
    int i, j, k;

    scanf("%d%d", &N, &M);
    for(i = 1; i <= M; i++) scanf("%d%d", A+i, B+i);

    init();
    for(i = 1; i <= M; i++) if(merge(A[i], B[i])) R[++RN] = i;

    init();
    for(i = M; i > 0; i--) if(merge(A[i], B[i])) R[++RN] = i;

    scanf("%d", &Q);
    while(Q--) {
        int x, y, ret = 0;
        scanf("%d%d", &x, &y);

        init();
        for(i = 1; i <= RN; i++) {
            if(R[i] < x || y < R[i]) merge(A[R[i]], B[R[i]]);
        }
        for(i = 1; i <= N; i++) if(get(i) == i) ++ret;
        printf("%d\n", ret);
    }
    return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 1880 KB Output is correct
2 Correct 36 ms 1880 KB Output is correct
3 Correct 44 ms 1880 KB Output is correct
4 Correct 44 ms 1880 KB Output is correct
5 Correct 48 ms 1880 KB Output is correct
6 Correct 408 ms 1880 KB Output is correct
7 Correct 356 ms 1880 KB Output is correct
8 Correct 400 ms 1880 KB Output is correct
9 Correct 40 ms 1880 KB Output is correct
10 Correct 40 ms 1880 KB Output is correct
11 Correct 40 ms 1880 KB Output is correct
12 Correct 44 ms 1880 KB Output is correct
13 Correct 44 ms 1880 KB Output is correct
14 Correct 40 ms 1880 KB Output is correct
15 Correct 40 ms 1880 KB Output is correct
16 Correct 40 ms 1880 KB Output is correct
17 Correct 32 ms 1880 KB Output is correct
18 Correct 28 ms 1880 KB Output is correct
19 Correct 16 ms 1880 KB Output is correct
20 Correct 16 ms 1880 KB Output is correct
21 Correct 4 ms 1880 KB Output is correct
22 Correct 4 ms 1880 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1500 ms 1880 KB Output is correct
2 Correct 1316 ms 1880 KB Output is correct
3 Correct 1800 ms 1880 KB Output is correct
4 Correct 1568 ms 1880 KB Output is correct
5 Correct 1476 ms 1880 KB Output is correct
6 Correct 1428 ms 1880 KB Output is correct
7 Correct 1728 ms 1880 KB Output is correct
8 Correct 1672 ms 1880 KB Output is correct
9 Correct 1556 ms 1880 KB Output is correct
10 Correct 1540 ms 1880 KB Output is correct
11 Correct 1468 ms 1880 KB Output is correct
12 Correct 1456 ms 1880 KB Output is correct
13 Correct 1680 ms 1880 KB Output is correct
14 Correct 1544 ms 1880 KB Output is correct
15 Correct 1480 ms 1880 KB Output is correct
16 Correct 1444 ms 1880 KB Output is correct
17 Correct 1272 ms 1880 KB Output is correct
18 Correct 1216 ms 1880 KB Output is correct
19 Correct 540 ms 1880 KB Output is correct
20 Correct 700 ms 1880 KB Output is correct
21 Correct 156 ms 1880 KB Output is correct
22 Correct 160 ms 1880 KB Output is correct