oj.uz

답안 #13038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13038 2015-01-26T15:41:41 Z gs14004 간선 파괴 (GA5_destroy) C++14
100 / 100
 995 ms 2196 KB 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
struct disj{
    int pa[707], r[707];
    void init(int n){
        memset(r,0,sizeof(r));
        for(int i=0; i<=n; i++) pa[i] = i;
    }
    int find(int x){
        if(pa[x] == x) return x;
        else return pa[x] = find(pa[x]);
    }
    int uni(int p, int q){
        p = find(p);
        q = find(q);
        if(p == q) return 0;
        if(r[p] > r[q]) pa[q] = p;
        else pa[p] = q;
        if(r[p] == r[q]) r[p]++;
        return 1;
    }
}disj;
 
int n,m;
int u[125000], v[125000];
 
vector<int> inc, dec;
int main(){
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        scanf("%d %d",&u[i],&v[i]);
    }
    disj.init(n);
    for (int i=0; i<m; i++) {
        if(disj.uni(u[i],v[i])){
            inc.push_back(i+1);
        }
    }
    disj.init(n);
    for (int i=m-1; i>=0; i--) {
        if(disj.uni(u[i],v[i])){
            dec.push_back(i+1);
        }
    }
    int q;
    scanf("%d",&q);
    while (q--) {
        int x,y;
        scanf("%d %d",&x,&y);
        disj.init(n);
        int cnt = n;
        for (int i : inc) {
            if(i <= x-1){
                cnt -= disj.uni(u[i-1],v[i-1]);
            }
            else break;
        }
        for (int i : dec) {
            if(i >= y+1){
                cnt -= disj.uni(u[i-1],v[i-1]);
            }
            else break;
        }
        printf("%d\n",cnt);
    }
}

Subtask #1
25.0 / 25.0

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

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2196 KB Output is correct
2 Correct 22 ms 2196 KB Output is correct
3 Correct 23 ms 2196 KB Output is correct
4 Correct 29 ms 2196 KB Output is correct
5 Correct 30 ms 2196 KB Output is correct
6 Correct 197 ms 2196 KB Output is correct
7 Correct 197 ms 2196 KB Output is correct
8 Correct 198 ms 2196 KB Output is correct
9 Correct 27 ms 2196 KB Output is correct
10 Correct 27 ms 2196 KB Output is correct
11 Correct 27 ms 2196 KB Output is correct
12 Correct 32 ms 2196 KB Output is correct
13 Correct 24 ms 2196 KB Output is correct
14 Correct 20 ms 2196 KB Output is correct
15 Correct 20 ms 2196 KB Output is correct
16 Correct 28 ms 2196 KB Output is correct
17 Correct 9 ms 2196 KB Output is correct
18 Correct 3 ms 2196 KB Output is correct
19 Correct 2 ms 2196 KB Output is correct
20 Correct 3 ms 2196 KB Output is correct
21 Correct 2 ms 2196 KB Output is correct
22 Correct 2 ms 2196 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 720 ms 2196 KB Output is correct
2 Correct 737 ms 2196 KB Output is correct
3 Correct 693 ms 2196 KB Output is correct
4 Correct 757 ms 2196 KB Output is correct
5 Correct 797 ms 2196 KB Output is correct
6 Correct 667 ms 2196 KB Output is correct
7 Correct 700 ms 2196 KB Output is correct
8 Correct 799 ms 2196 KB Output is correct
9 Correct 969 ms 2196 KB Output is correct
10 Correct 995 ms 2196 KB Output is correct
11 Correct 698 ms 2196 KB Output is correct
12 Correct 666 ms 2196 KB Output is correct
13 Correct 710 ms 2196 KB Output is correct
14 Correct 687 ms 2196 KB Output is correct
15 Correct 888 ms 2196 KB Output is correct
16 Correct 846 ms 2196 KB Output is correct
17 Correct 361 ms 2196 KB Output is correct
18 Correct 340 ms 2196 KB Output is correct
19 Correct 106 ms 2196 KB Output is correct
20 Correct 137 ms 2196 KB Output is correct
21 Correct 42 ms 2196 KB Output is correct
22 Correct 35 ms 2196 KB Output is correct