oj.uz

Submission #13037

# Submission time Handle Problem Language Result Execution time Memory
13037 2015-01-26T15:40:20 Z gs14004 간선 파괴 (GA5_destroy) C++14
0 / 100
 13 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(inc[i] <= x-1){
                cnt -= disj.uni(u[inc[i]-1],v[inc[i]-1]);
            }
            else break;
        }
        for (int i : dec) {
            if(dec[i] >= y+1){
                cnt -= disj.uni(u[dec[i]-1],v[dec[i]-1]);
            }
            else break;
        }
        printf("%d\n",cnt);
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 2192 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -