Submission #494785

#	Time	Username	Problem	Language	Result	Execution time	Memory
494785		abc864197532	Parachute rings (IOI12_rings)	C++17	100 / 100	2015 ms	119460 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define X first
#define Y second
#define pii pair<int, int>
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
    cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args);
#include "grader_B.cpp"
#else
#define test(args...) void(0);
#endif
const int N = 1000000;

vector <pii> edge;
vector <int> adj[N];
int deg[N], n, mx, id[N];
bool grt, dead[4];

struct Dsu {
    int dsu[N], sz[N];
    bool cyc;
    
    void init(int n) {
        iota(dsu, dsu + n, 0);
        fill(sz, sz + n, 1);
        cyc = false;
    }

    int Find(int x) {
        if (dsu[x] == x)
            return x;
        return dsu[x] = Find(dsu[x]);
    }
    bool Union(int u, int v) {
        u = Find(u), v = Find(v);
        if (u == v)
            return cyc = true;
        dsu[u] = v;
        sz[v] += sz[u];
        return false;
    }
} ord, p[4];

void Init(int N) {
    n = mx = N;
    ord.init(n);
    for (int i : {0, 1, 2, 3})
        p[i].init(n);
}

void gen(int v) {
    assert(deg[v] == 3);
    id[0] = v;
    for (int i : {1, 2, 3})
        id[i] = adj[v][i - 1];
    for (int i = 0; i < 4; ++i) {
        int v = id[i];
        for (pii A : edge) {
            if (A.X != v && A.Y != v) {
                p[i].Union(A.X, A.Y);
            }
        }
    }
}

void upd(int v) {
    if (deg[v] == 3) {
        for (int i = 0; i < 4; ++i) {
            bool is = (v == id[i]);
            for (int u : adj[v]) 
                if (u == id[i])
                    is = true;
            if (!is)
                dead[i] = true;
        }
    } else {
        for (int i = 0; i < 4; ++i) if (id[i] != v)
            dead[i] = true;
    }
}

void Link(int a, int b) {
    deg[a]++, deg[b]++;
    adj[a].pb(b), adj[b].pb(a);
    if (deg[a] >= 3) {
        if (!grt)
            gen(a), grt = true;
        else
            upd(a);
    }
    if (deg[b] >= 3) {
        if (!grt)
            gen(b), grt = true;
        else
            upd(b);
    }
    if (grt) {
        for (int i = 0; i < 4; ++i) if (a != id[i] && b != id[i]) {
            p[i].Union(a, b);
        }
    } else {
        edge.eb(a, b);
        if (ord.Union(a, b)) {
            if (mx == n)
                mx = ord.sz[ord.Find(a)];
            else
                mx = 0;
        }
    }
}

int CountCritical() {
    if (grt) {
        int ans = 0;
        for (int i = 0; i < 4; ++i) if (!dead[i])
            ans += !p[i].cyc;
        return ans;
    } else {
        return mx;
    }
}

/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/

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