제출 #483234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483234		syl123456	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	983 ms	107556 KiB

rings

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

vector<int> deg, rt, stk, ring;
vector<int> v;
vector<vector<int>> g;
vector<bool> vis;
bool fail, first;
int n;

int find(int i) {
    return rt[i] = rt[i] == i ? i : find(rt[i]);
}

void dfs(int i, int p) {
    vis[i] = true;
    stk.push_back(i);
    for (int j : g[i])
        if (j != p) {
            if (!vis[j])
                dfs(j, i);
            else {
                while (stk.back() != j)
                    ring.push_back(stk.back()), stk.pop_back();
                ring.push_back(j);
                return;
            }
            if (!ring.empty())
                return;
        }
    stk.pop_back();
}

void upd(vector<int> tmp) {
    if (fail)
        return;
    if (v.empty()) {
        v = tmp;
        return;
    }
    for (int i = 0; i < (int)v.size(); ) {
        bool find = false;
        for (int j : tmp)
            if (v[i] == j) {
                find = true;
            }
        if (!find)
            swap(v[i], v.back()), v.pop_back();
        else
            ++i;
    }
    if (v.empty())
        fail = true;
}

void Init(int N) {
    deg.assign(N, 0);
    rt.resize(N);
    iota(all(rt), 0);
    vis.assign(N, false);
    g.assign(N, vector<int>());
    fail = false, first = true;
    n = N;
}

void Link(int x, int y) {
    if (fail)
        return;
    ++deg[x], ++deg[y];
    g[x].push_back(y), g[y].push_back(x);
    if (deg[x] == 4) {
        vector<int> tmp(1, x);
        upd(tmp);
    }
    else if (deg[x] == 3) {
        vector<int> tmp = g[x];
        tmp.push_back(x);
        upd(tmp);
    }
    if (fail)
        return;
    if (deg[y] == 4) {
        vector<int> tmp(1, y);
        upd(tmp);
    }
    else if (deg[y] == 3) {
        vector<int> tmp = g[y];
        tmp.push_back(y);
        upd(tmp);
    }
    if (fail)
        return;
    if (find(x) == find(y)) {
        if (first) {
            first = false;
            dfs(x, -1);
            debug(ring);
            upd(ring);
        }
        else if (!v.empty() && find(v.back()) != find(x))
            fail = true;
    }
    else {
        rt[find(x)] = find(y);
    }
}

int CountCritical() {
    if (fail)
        return 0;
    if (v.empty())
        return n;
    return v.size();
}

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