oj.uz

Submission #13008

# Submission time Handle Problem Language Result Execution time Memory
13008 2015-01-24T08:03:58 Z gs14004 간선 파괴 (GA5_destroy) C++
0 / 100
 1656 ms 2192 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]);
    }
    void uni(int p, int q){
        p = find(p);
        q = find(q);
        if(r[p] > r[q]) pa[q] = p;
        else pa[p] = q;
        if(r[p] == r[q]) r[p]++;
    }
}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.find(u[i]) != disj.find(v[i])){
            disj.uni(u[i],v[i]);
            inc.push_back(i+1);
        }
    }
    disj.init(n);
    for (int i=m-1; i>=0; i--) {
        if(disj.find(u[i]) != disj.find(v[i])){
            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);
        for (int i=0; i<inc.size(); i++) {
            if(inc[i] <= x){
                disj.uni(u[inc[i]-1],v[inc[i]-1]);
            }
        }
        for (int i=0; i<inc.size(); i++) {
            if(dec[i] >= y){
                disj.uni(u[dec[i]-1],v[dec[i]-1]);
            }
        }
        int cnt = 0;
        for (int i=1; i<=n; i++) {
            if(disj.find(i) == i) cnt++;
        }
        printf("%d\n",cnt);
    }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2192 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 44 ms 2192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

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