제출 #568342

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

rings

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int n;
int p[N], sz[N], esz[N];
bool not_in[N];
vi G[N], g[N], s;

void Init(int _n) {
    n = _n;
    for(int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
        s.PB(i);
    }
}

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void unite(int u, int v) {
    u = find(u), v = find(v);
    assert(u != v);
    if(sz[u] > sz[v]) swap(u, v);
    p[u] = v;
    sz[v] += sz[u];
    esz[v] += esz[u];
}

V<pi> tt;
int cc = 0, bad_cnt = 0;

void inter(vi ss) {
    vi tmp;
    for(int u:s) if(find(ALL(ss), u) != ss.end())
        tmp.PB(u);
    swap(tmp, s);
}

void check(int u) {
    if(SZ(g[u]) <= 2) return;
    bad_cnt++;
    if(SZ(g[u]) > 3)
        inter({u});
    inter({u, g[u][0], g[u][1], g[u][2]});
}

void Link(int u, int v) {
    if(find(u) != find(v)) {
        if(esz[find(u)] >= sz[find(u)]) cc--;
        if(esz[find(v)] >= sz[find(v)]) cc--;
        unite(u, v);
        esz[find(u)]++;
        if(esz[find(u)] >= sz[find(u)]) cc++;
        G[u].PB(v);
        G[v].PB(u);
    } else {
        if(esz[find(u)] >= sz[find(u)]) cc--;
        esz[find(u)]++;
        if(esz[find(u)] >= sz[find(u)]) cc++;

        tt.EB(u, v);
        // if(SZ(tt) <= 2) {
        //     vi stk;
        //     function<void(int, int)> dfs = [&] (int x, int pa) {
        //         stk.PB(x);
        //         if(x == v) {
        //             V<bool> vis(n);
        //             for(int i:stk) vis[i] = true;
        //             for(int i = 0; i < n; i++) if(!vis[i])
        //                 not_in[i] = true;
        //         }
        //         for(int y:g[x]) if(y != pa) {
        //             dfs(y, x);
        //         }
        //         stk.pop_back();
        //     };
        // } 
    }
    g[u].PB(v);
    g[v].PB(u);
    check(u), check(v);
}

bool ok(int u) {
    // if(SZ(tt) > 2) return false;
    // if(not_in[u]) return false;
    // return true;
    V<bool> vis(n);
    bool has_cycle = false;
    function<void(int, int)> dfs = [&] (int x, int pa) {
        vis[x] = true;
        for(int y:g[x]) if(y != pa && y != u) {
            if(vis[y]) has_cycle = true;
            else dfs(y, x);
        }
    };
    for(int i = 0; i < n; i++) if(!vis[i] && i != u)
        dfs(i, -1);
    return !has_cycle;
}

int CountCritical() {
    if(cc > 1) return 0;
    if(s.empty()) return 0;
    if(cc == 0) return SZ(s);
    if(esz[find(s[0])] < sz[find(s[0])]) return 0;
    if(bad_cnt == 1) {
        if(SZ(s) == 1) return 1;
        return 3;
    }
    int ans = 0;
    for(int u:s)
        if(ok(u)) ans++;
    return ans;
}

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