Submission #65789

#	Time	Username	Problem	Language	Result	Execution time	Memory
65789		aquablitz11	Parachute rings (IOI12_rings)	C++14	20 / 100	4106 ms	157292 KiB

rings

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e6+10;
 
int n;
set<int> G[N];
vector<pii> E;
 
// maintaining list of test nodes
 
int c02;
set<int> d3, d4;
 
inline void movenode(int u, int a, int b)
{
    if (a <= 2) --c02;
    if (a == 3) d3.erase(u);
    if (a >= 4) d4.erase(u);
    if (b <= 2) ++c02;
    if (b == 3) d3.insert(u);
    if (b >= 4) d4.insert(u);
}
 
inline set<int> testnodes()
{
    if (d3.size() == 0 && d4.size() == 0) return set<int>();
    if (d4.size() > 0) return d4;
    set<int> ans = d3;
    for (auto u : d3) {
        for (auto v : G[u])
            ans.insert(v);
    }
    return ans;
}
 
inline bool cancut(int u) {
    if (d4.size() > 0) return d4.count(u);
    if (d3.size() > 0) return d3.count(u);
    return false;
}
 
// disjoint set
 
int par[N];
bool mergefail = false;
int root(int u) {
    if (par[u] == u) return u;
    return par[u] = root(par[u]);
}
inline void merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) mergefail = true;
    else par[u] = v;
}
/*inline void builddsu() {
    mergefail = false;
    for (int u = 0; u < n; ++u)
        par[u] = u;
    for (auto e : E) {
        int u = e.first, v = e.second;
        if (!cancut(u) && !cancut(v))
            merge(u, v);
    }
}
int _np[N], _nv[N], tick;
inline int &np(int u) {
    if (_nv[u] != tick) {
        _np[u] = par[u];
        _nv[u] = tick;
    }
    return _np[u];
}
int newroot(int u) {
    if (np(u) == u) return u;
    return np(u) = newroot(np(u));
}
inline bool newmerge(int u, int v) {
    u = newroot(u), v = newroot(v);
    if (u == v) return false;
    np(u) = v;
    return true;
}*/
 
// testing system:
 
bool checkcycle(int x)
{
    mergefail = false;
    for (int u = 0; u < n; ++u)
        par[u] = u;
    for (auto e : E) {
        int u = e.first, v = e.second;
        if (u == x || v == x) continue;
        merge(u, v);
        if (mergefail) return false;
    }
    return true;
}
 
bool dead[N];
bool test(int u)
{
    if (dead[u]) return false;
 
    movenode(u, G[u].size(), 0);
    for (auto v : G[u])
        movenode(v, G[v].size(), G[v].size()-1);
 
    //++tick;
    bool ans = d3.size() == 0 && d4.size() == 0 && checkcycle(u);
 
    movenode(u, 0, G[u].size());
    for (auto v : G[u])
        movenode(v, G[v].size()-1, G[v].size());
 
    if (!ans) dead[u] = true;
    return ans;
}
 
// problems:
 
void Init(int n) {
    ::n = n;
}
 
void Link(int a, int b) {
    E.emplace_back(a, b);
    movenode(a, G[a].size(), G[a].size()+1);
    movenode(b, G[b].size(), G[b].size()+1);
    G[a].insert(b);
    G[b].insert(a);
}
 
int mnans = 1e9;
int CountCritical() {
    if (mnans == 0 || d4.size() > 1 || d3.size() > 4)
        return mnans = 0;
    if (d3.size() == 0 && d4.size() == 0 && checkcycle(-1))
        return mnans = n;
    int cnt = 0;
    for (int u = 0; u < n; ++u) if (test(u)) ++cnt;
    return mnans = cnt;
}

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