oj.uz

Submission #1111296

# Submission time Handle Problem Language Result Execution time Memory
1111296 2024-11-12T02:12:45 Z lmToT27 Parachute rings (IOI12_rings) C++17
0 / 100
 4000 ms 47548 KB 
#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"
        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);
                for (int i = 0; i < m; i++) addEg(eg[i].first, eg[i].second);
        }
};

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

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

void Init(int _n) {
        n = _n;
        iota(pa + 1, pa + n + 1, 1);
        fill(sz + 0, sz + n + 1, 1);
}

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 {
                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 (auto &G : subGraphs) res += G.valid;
                return res;
        }
        if (circleSize) return circleSize;
        return n;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8272 KB Output is correct
2 Correct 161 ms 47468 KB Output is correct
3 Correct 165 ms 47452 KB Output is correct
4 Correct 33 ms 8272 KB Output is correct
5 Correct 80 ms 8444 KB Output is correct
6 Correct 128 ms 8520 KB Output is correct
7 Correct 64 ms 47424 KB Output is correct
8 Correct 97 ms 8272 KB Output is correct
9 Incorrect 165 ms 47548 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 21480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8272 KB Output is correct
2 Correct 161 ms 47468 KB Output is correct
3 Correct 165 ms 47452 KB Output is correct
4 Correct 33 ms 8272 KB Output is correct
5 Correct 80 ms 8444 KB Output is correct
6 Correct 128 ms 8520 KB Output is correct
7 Correct 64 ms 47424 KB Output is correct
8 Correct 97 ms 8272 KB Output is correct
9 Incorrect 165 ms 47548 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8272 KB Output is correct
2 Correct 161 ms 47468 KB Output is correct
3 Correct 165 ms 47452 KB Output is correct
4 Correct 33 ms 8272 KB Output is correct
5 Correct 80 ms 8444 KB Output is correct
6 Correct 128 ms 8520 KB Output is correct
7 Correct 64 ms 47424 KB Output is correct
8 Correct 97 ms 8272 KB Output is correct
9 Incorrect 165 ms 47548 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8272 KB Output is correct
2 Correct 161 ms 47468 KB Output is correct
3 Correct 165 ms 47452 KB Output is correct
4 Correct 33 ms 8272 KB Output is correct
5 Correct 80 ms 8444 KB Output is correct
6 Correct 128 ms 8520 KB Output is correct
7 Correct 64 ms 47424 KB Output is correct
8 Correct 97 ms 8272 KB Output is correct
9 Incorrect 165 ms 47548 KB Output isn't correct
10 Halted 0 ms 0 KB -