제출 #15601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15601		gs14004	낙하산 고리들 (IOI12_rings)	C++14	0 / 100	4022 ms	209020 KiB

rings

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<int> graph[1000005];
int n;
int deg[1000005];
int focus = -1;
bool deadend = 0;

vector<int> v;
int bad[4];

struct disj{
    int pa[1000005];
    int degcnt[1000005][5];
    int degx[1000005];
    int size[1000005];
    int without;

    void init(int n, int w){
        without = w;
        memset(degcnt, 0, sizeof(degcnt));
        memset(degx, 0, sizeof(degx));
        for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, size[i] = 1;
    }
 
    int find(int x){
        return pa[x] = (pa[x] == x ? x : find(pa[x]));
    }
 
    void uni(int p, int q){
        if(p == without || q == without) return;
        degx[p]++;
        if(degx[p] <= 4){
            degcnt[find(p)][degx[p]-1]--;
            degcnt[find(p)][degx[p]]++;
        }
        degx[q]++;
        if(degx[q] <= 4){
            degcnt[find(q)][degx[q]-1]--;
            degcnt[find(q)][degx[q]]++;
        }
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p; find(q);
        for(int i=0; i<5; i++){
            degcnt[p][i] += degcnt[q][i];
        }
        size[p] += size[q];
    }

    bool ckBad(int x){
        x = find(x);
        return (degcnt[x][4] || degcnt[x][3] || (degcnt[x][2] && !degcnt[x][1]));
    }
}disj, wotree[4];
 
void Init(int N){
    n = N; 
    disj.init(n,-1);
}

void Link(int A, int B){
    deg[A]++, deg[B]++;
    if(deg[A] <= deg[B]){
        swap(A,B);
    }
    if(deg[A] == 3 && v.empty()){
        v.push_back(A);
        v.push_back(B);
        for(auto &i : graph[A]){
            v.push_back(i);
        }
        for(int i=0; i<v.size(); i++){
            wotree[i].init(n,v[i]);
            for(int j=0; j<n; j++){
                for(auto &k : graph[j]){
                    if(j < k) wotree[i].uni(j,k);
                }
            }
            for(int j=0; j<n; j++){
                if(wotree[i].ckBad(j)){
                    bad[i] = 1;
                }
            }
        }
    }
    graph[A].push_back(B);
    graph[B].push_back(A);
    disj.uni(A,B);
    if(v.empty()){
        if(disj.ckBad(A)){
            if(focus == -1){
                focus = A;
            }
            else if(disj.find(focus) != disj.find(A)){
                deadend = 1;
            }
        }
    }
    else{
        for(int i=0; i<v.size(); i++){
            wotree[i].uni(A,B);
            if(wotree[i].ckBad(A)){
                bad[i] = 1;
            }
        }
    }
}

 
int CountCritical(){
    if(deadend == 1) return 0;
    if(disj.without != -1) return 1;
    else if(!v.empty()){
        int cnt = 0;
        for(int i=0; i<v.size(); i++){
            if(!bad[i]) cnt++;
        }
        return cnt;
    }
    else{ 
        if(focus == -1) return n;
        return disj.size[focus];
    }
}

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'void Link(int, int)':
rings.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~
rings.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:120:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v.size(); i++){
                      ~^~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31