Submission #1111291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111291		lmToT27	Parachute rings (IOI12_rings)	C++17	0 / 100	4064 ms	71104 KiB

rings

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()

typedef long long ll;

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 1e6 + 3;
const ll MOD[] = {1000000007, 998244353};

int n, q;
bool badGraph; // no solulu for this graph
vector <int> adj[MAX];
vector <pair <int, int>> curEg;
int circleSize;

struct graph_t { // graph G after deleting vertex "deleted"
        bool valid; // checking whether graph G is perfect or not
        int deleted; // vertex we deleted from the graph
        int deg[MAX], pa[MAX];

        int findpa(int u) {
                return u == pa[u] ? u : pa[u] = findpa(pa[u]);
        }

        void join(int u, int v) {
                deg[u]++;
                deg[v]++;
                u = findpa(u);
                v = findpa(v);
                pa[v] = u;
        }

        void addEg(int u, int v) {
                if (u == deleted || v == deleted || !valid) return;
                if (deg[u] == 2 || deg[v] == 2 || findpa(u) == findpa(v)) return void(valid = 0); // graph must not contain cycle or with deg >= 3
                join(u, v);
        }

        graph_t(int chosen) {
                valid = 1;
                deleted = chosen;
                iota(pa + 1, pa + n + 1, 1);
                fill(deg + 1, deg + n + 1, 0);
                for (auto &[u, v] : curEg) addEg(u, v);
        }
};

int pa[MAX], sz[MAX];
vector <graph_t> subGraphs;

int findpa(int u) {
        return u == pa[u] ? u : pa[u] = findpa(pa[u]);
}

bool join(int u, int v) {
        u = findpa(u);
        v = findpa(v);
        if (u != v) {
                pa[v] = u;
                sz[u] += sz[v];
                return 1;
        }
        return 0;
}

void Link(int u, int v) {
        if (badGraph) return;
        if (subGraphs.size()) for (auto &G : subGraphs) G.addEg(u, v);
        else {
                if (adj[u].size() < adj[v].size()) swap(u, v);
                curEg.push_back(make_pair(u, v));
                adj[u].push_back(v);
                adj[v].push_back(u);
                if ((int)adj[u].size() == 3) { // if there's an vertex with deg >= 3, then the answer must be itself or its adjacent vertex
                        // We create some subGraphs
                        subGraphs.push_back(graph_t(u));
                        for (int &v : adj[u]) subGraphs.push_back(graph_t(v));
                } else {
                        if (!join(u, v)) {
                                if (circleSize != 0) badGraph = 1;
                                else circleSize = sz[findpa(u)];
                        }
                }
        }
}

int CountCritical() {
        if (badGraph) return 0;
        if (subGraphs.size()) {
                int res = 0;
                for (auto &G : subGraphs) res += G.valid;
                return res;
        }
        if (circleSize) return circleSize;
        return n;
}

void Init(int _n) {
        n = _n;
}

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