Submission #483387

#	Time	Username	Problem	Language	Result	Execution time	Memory
483387		syl123456	Parachute rings (IOI12_rings)	C++17	100 / 100	1248 ms	102196 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<vector<int>> deg, pa, g;
vector<bool> fail;
vector<int> v, sz, id;
int n, ans;

int extend() {
    deg.emplace_back(n, 0);
    pa.emplace_back(n);
    iota(all(pa.back()), 0);
    fail.push_back(false);
    assert(deg.size() <= 5);
    return deg.size() - 1;
}

int find(int _id, int i) {
    return pa[_id][i] = pa[_id][i] == i ? i : find(_id, pa[_id][i]);
}

void upd(vector<int> tmp) {
    if (fail[0])
        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[0] = true;
}

void add(int _id, pi _e) {
    if (fail[_id])
        return;
    int x = _e.first, y = _e.second;
    if (++deg[_id][x] >= 3) {
        fail[_id] = true;
        return;
    }
    if (++deg[_id][y] >= 3) {
        fail[_id] = true;
        return;
    }
    x = find(_id, x), y = find(_id, y);
    if (x == y) {
        fail[_id] = true;
        return;
    }
    pa[_id][x] = y;
}

vector<pi> e;

void Init(int N) {
    ans = n = N;
    extend();
    g.resize(n);
    sz.assign(n, 1);
    id.assign(n, -1);
}

void Link(int x, int y) {
    if (fail[0])
        return;
    ++deg[0][x], ++deg[0][y];
    g[x].push_back(y), g[y].push_back(x);
    e.emplace_back(x, y);
    if (deg[0][x] == 4) {
        vector<int> tmp(1, x);
        upd(tmp);
    }
    else if (deg[0][x] == 3) {
        vector<int> tmp = g[x];
        tmp.push_back(x);
        upd(tmp);
    }
    if (deg[0][y] == 4) {
        vector<int> tmp(1, y);
        upd(tmp);
    }
    else if (deg[0][y] == 3) {
        vector<int> tmp = g[y];
        tmp.push_back(y);
        upd(tmp);
    }
    x = find(0, x), y = find(0, y);
    if (x == y) {
        if (!fail[0] && v.empty()) {
            if (ans == n)
                ans = sz[x];
            else
                ans = 0;
        }
    }
    else
        pa[0][x] = y, sz[y] += sz[x];
}

int CountCritical() {
    if (fail[0])
        return 0;
    if (v.empty())
        return ans;
    vector<int> tmp;
    for (int i : v) {
        if (id[i] == -1)
            id[i] = extend();
        for (pi j : e)
            if (j.first != i && j.second != i)
                add(id[i], j);
        if (!fail[id[i]])
            tmp.push_back(i);
    }
    e.clear();
    upd(tmp);
    return v.size();
}

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