oj.uz

Submission #1111304

# Submission time Handle Problem Language Result Execution time Memory
1111304 2024-11-12T02:42:55 Z lmToT27 Parachute rings (IOI12_rings) C++17
52 / 100
 4000 ms 49880 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"
        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;
		for (int i = 0; i < n; i++) pa[i] = i, deg[i] = 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;
        for (int i = 0; i < n; i++) pa[i] = i, sz[i] = 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8272 KB Output is correct
2 Correct 147 ms 47516 KB Output is correct
3 Correct 170 ms 47656 KB Output is correct
4 Correct 32 ms 8272 KB Output is correct
5 Correct 76 ms 8404 KB Output is correct
6 Correct 133 ms 8472 KB Output is correct
7 Correct 60 ms 47552 KB Output is correct
8 Correct 97 ms 8440 KB Output is correct
9 Correct 167 ms 47560 KB Output is correct
10 Correct 161 ms 47552 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8272 KB Output is correct
2 Correct 147 ms 47516 KB Output is correct
3 Correct 170 ms 47656 KB Output is correct
4 Correct 32 ms 8272 KB Output is correct
5 Correct 76 ms 8404 KB Output is correct
6 Correct 133 ms 8472 KB Output is correct
7 Correct 60 ms 47552 KB Output is correct
8 Correct 97 ms 8440 KB Output is correct
9 Correct 167 ms 47560 KB Output is correct
10 Correct 161 ms 47552 KB Output is correct
11 Correct 171 ms 47556 KB Output is correct
12 Correct 293 ms 47632 KB Output is correct
13 Correct 289 ms 47552 KB Output is correct
14 Correct 202 ms 47668 KB Output is correct
15 Correct 201 ms 47560 KB Output is correct
16 Correct 240 ms 8528 KB Output is correct
17 Correct 275 ms 47532 KB Output is correct
18 Correct 282 ms 47892 KB Output is correct
19 Correct 248 ms 8528 KB Output is correct
20 Correct 289 ms 47808 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8272 KB Output is correct
2 Correct 147 ms 47516 KB Output is correct
3 Correct 170 ms 47656 KB Output is correct
4 Correct 32 ms 8272 KB Output is correct
5 Correct 76 ms 8404 KB Output is correct
6 Correct 133 ms 8472 KB Output is correct
7 Correct 60 ms 47552 KB Output is correct
8 Correct 97 ms 8440 KB Output is correct
9 Correct 167 ms 47560 KB Output is correct
10 Correct 161 ms 47552 KB Output is correct
11 Correct 171 ms 47556 KB Output is correct
12 Correct 293 ms 47632 KB Output is correct
13 Correct 289 ms 47552 KB Output is correct
14 Correct 202 ms 47668 KB Output is correct
15 Correct 201 ms 47560 KB Output is correct
16 Correct 240 ms 8528 KB Output is correct
17 Correct 275 ms 47532 KB Output is correct
18 Correct 282 ms 47892 KB Output is correct
19 Correct 248 ms 8528 KB Output is correct
20 Correct 289 ms 47808 KB Output is correct
21 Correct 682 ms 10056 KB Output is correct
22 Correct 1043 ms 10760 KB Output is correct
23 Correct 1346 ms 11420 KB Output is correct
24 Correct 1367 ms 48116 KB Output is correct
25 Correct 242 ms 48328 KB Output is correct
26 Correct 1638 ms 49600 KB Output is correct
27 Correct 2083 ms 11748 KB Output is correct
28 Correct 2172 ms 49584 KB Output is correct
29 Correct 771 ms 49880 KB Output is correct
30 Correct 2523 ms 11312 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8272 KB Output is correct
2 Correct 147 ms 47516 KB Output is correct
3 Correct 170 ms 47656 KB Output is correct
4 Correct 32 ms 8272 KB Output is correct
5 Correct 76 ms 8404 KB Output is correct
6 Correct 133 ms 8472 KB Output is correct
7 Correct 60 ms 47552 KB Output is correct
8 Correct 97 ms 8440 KB Output is correct
9 Correct 167 ms 47560 KB Output is correct
10 Correct 161 ms 47552 KB Output is correct
11 Execution timed out 4067 ms 22200 KB Time limit exceeded
12 Halted 0 ms 0 KB -