제출 #13010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13010		gs14004	간선 파괴 (GA5_destroy)	C++98	100 / 100	1093 ms	2200 KiB

destroy

#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=0; i<inc.size(); i++) {
            if(inc[i] <= x-1){
                cnt -= disj.uni(u[inc[i]-1],v[inc[i]-1]);
            }
            else break;
        }
        for (int i=0; i<dec.size(); i++) {
            if(dec[i] >= y+1){
                cnt -= disj.uni(u[dec[i]-1],v[dec[i]-1]);
            }
            else break;
        }
        printf("%d\n",cnt);
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40