제출 #736574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736574		horiseun	Parachute rings (IOI12_rings)	C++17	52 / 100	4042 ms	71944 KiB

rings

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

#define f first
#define s second

int n, cycsz;
bool nne;
vector<int> adj[1000005];
vector<pair<int, int>> edges;

struct UnionFind1 {
    int rt, par[1000005], deg[1000005];
    bool vld;

    int find(int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }

    void merge(int x, int y) {
        if (!vld || x == rt || y == rt) return;
        int px = find(x), py = find(y);
        if (deg[x] == 2 || deg[y] == 2 || px == py) {
            vld = false;
            return;
        }
        deg[x]++;
        deg[y]++;
        par[px] = py;
    }
    
    UnionFind1(int root) {
        rt = root;
        vld = true;
        for (int i = 0; i < n; i++) {
            par[i] = i;
            deg[i] = 0;
        }
        for (pair<int, int> edge : edges) {
            merge(edge.f, edge.s);
        }
    }
};

int par[1000005], sz[1000005];
vector<UnionFind1> uf;

static int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

static bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    sz[x] += sz[y];
    par[y] = x;
    return true;
}

void Init(int N) {
    n = N;
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
}

int CountCritical() {
    if (nne) return 0;
    if (!uf.empty()) {
        int ans = 0;
        for (int i = 0; i < uf.size(); i++) {
            ans += uf[i].vld;
        }
        return ans;
    } else if (cycsz) return cycsz;
    return n;
}

void Link(int a, int b) {
    if (nne) return;
    if (!uf.empty()) {
        for (int i = 0; i < uf.size(); i++) {
            uf[i].merge(a, b);
        }
        return;
    }
    edges.push_back({a, b});
    adj[a].push_back(b);
    adj[b].push_back(a);
    if (adj[a].size() < adj[b].size()) swap(a, b);
    if (adj[a].size() == 3) {
        uf.push_back(UnionFind1(a));
        for (int i : adj[a]) {
            uf.push_back(UnionFind1(i));
        }
        return;
    }
    if (!merge(a, b)) {
        if (cycsz) {
            nne = true;
            return;
        }
        cycsz = sz[find(a)];
    }
}

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

rings.cpp: In function 'int CountCritical()':
rings.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UnionFind1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i < uf.size(); i++) {
      |                         ~~^~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UnionFind1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < uf.size(); i++) {
      |                         ~~^~~~~~~~~~~

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