Submission #1111303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111303		lmToT27	Parachute rings (IOI12_rings)	C++17	52 / 100	4037 ms	49856 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;
pair <int, int> eg[MAX];
int m;

struct graph_t { // graph G after deleting vertex "deleted"
        int 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 (!valid || u == deleted || v == deleted) 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, pa + n, 0);
                fill(deg, deg + n, 0);
                for (int i = 0; i < m; i++) addEg(eg[i].first, eg[i].second);
        }
};

vector <graph_t> subGraphs;

int pa[MAX], sz[MAX];
bool badGraph; // no solulu for this graph
int adj[MAX][3], deg[MAX];
int circleSize;

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 Init(int _n) {
        n = _n;
        iota(pa, pa + n, 0);
        fill(sz, sz + n, 1);
}

void Link(int u, int v) {
        if (badGraph) return;
        if (subGraphs.size()) {
                for (int i = 0; i < (int)subGraphs.size(); i++) subGraphs[i].addEg(u, v);
        } else {
                eg[m++] = make_pair(u, v);
                adj[u][deg[u]++] = v;
                adj[v][deg[v]++] = u;
                if (deg[u] < deg[v]) swap(u, v);
                if (deg[u] == 3) {
                        subGraphs.push_back(graph_t(u));
                        for (int i = 0; i < 3; ++i) {
                                subGraphs.push_back(graph_t(adj[u][i]));
                        }
                        return;
                }
                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 (int i = 0; i < (int)subGraphs.size(); i++) res += subGraphs[i].valid;
                return res;
        }
        if (circleSize) return circleSize;
        return n;
}

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