oj.uz

Submission #736038

# Submission time Handle Problem Language Result Execution time Memory
736038 2023-05-05T07:02:45 Z horiseun Parachute rings (IOI12_rings) C++17
52 / 100
 4000 ms 79080 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

int n, cycsz;
bool nne;
vector<int> adj[1000005];
vector<pair<int, int>> edges;

struct UnionFind1 {
    int rt, par[1000005], deg[1000005];
    bool vld;

    int find(int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }

    void merge(int x, int y) {
        if (!vld || x == rt || y == rt) return;
        int px = find(x), py = find(y);
        if (deg[x] == 2 || deg[y] == 2 || px == py) {
            vld = false;
            return;
        }
        deg[x]++;
        deg[y]++;
        par[find(x)] = find(y);
    }
    
    UnionFind1(int root) {
        rt = root;
        vld = true;
        for (int i = 0; i < 1000005; i++) {
            par[i] = i;
            deg[i] = 0;
        }
        for (auto [a, b] : edges) {
            merge(a, b);
        }
    }
};

struct UnionFind2 {
    int par[1000005], sz[1000005];
    
    UnionFind2() {
        for (int i = 0; i < 1000005; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find(int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }
} cyc;

vector<UnionFind1> uf;

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

int CountCritical() {
    if (nne) return 0;
    if (!uf.empty()) {
        int ans = 0;
        for (int i = 0; i < uf.size(); i++) {
            ans += uf[i].vld;
        }
        return ans;
    } else if (cycsz) return cycsz;
    return n;
}

void Link(int a, int b) {
    if (nne) return;
    if (!uf.empty()) {
        for (int i = 0; i < uf.size(); i++) {
            uf[i].merge(a, b);
        }
        return;
    }
    edges.push_back({a, b});
    adj[a].push_back(b);
    adj[b].push_back(a);
    if (adj[a].size() < adj[b].size()) swap(a, b);
    if (adj[a].size() == 3) {
        uf.push_back(UnionFind1(a));
        for (int i : adj[a]) {
            uf.push_back(UnionFind1(i));
        }
        return;
    }
    if (!cyc.merge(a, b)) {
        if (cycsz) {
            nne = true;
            return;
        }
        cycsz = cyc.sz[cyc.find(a)];
    }
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UnionFind1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < uf.size(); i++) {
      |                         ~~^~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UnionFind1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < uf.size(); i++) {
      |                         ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 185 ms 78704 KB Output is correct
3 Correct 233 ms 78640 KB Output is correct
4 Correct 57 ms 39476 KB Output is correct
5 Correct 132 ms 39592 KB Output is correct
6 Correct 215 ms 39732 KB Output is correct
7 Correct 65 ms 78528 KB Output is correct
8 Correct 158 ms 39704 KB Output is correct
9 Correct 224 ms 78788 KB Output is correct
10 Correct 226 ms 78816 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 185 ms 78704 KB Output is correct
3 Correct 233 ms 78640 KB Output is correct
4 Correct 57 ms 39476 KB Output is correct
5 Correct 132 ms 39592 KB Output is correct
6 Correct 215 ms 39732 KB Output is correct
7 Correct 65 ms 78528 KB Output is correct
8 Correct 158 ms 39704 KB Output is correct
9 Correct 224 ms 78788 KB Output is correct
10 Correct 226 ms 78816 KB Output is correct
11 Correct 248 ms 78704 KB Output is correct
12 Correct 390 ms 79080 KB Output is correct
13 Correct 415 ms 78900 KB Output is correct
14 Correct 293 ms 78664 KB Output is correct
15 Correct 284 ms 78628 KB Output is correct
16 Correct 394 ms 40076 KB Output is correct
17 Correct 427 ms 78808 KB Output is correct
18 Correct 422 ms 78788 KB Output is correct
19 Correct 388 ms 39932 KB Output is correct
20 Correct 423 ms 79028 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 185 ms 78704 KB Output is correct
3 Correct 233 ms 78640 KB Output is correct
4 Correct 57 ms 39476 KB Output is correct
5 Correct 132 ms 39592 KB Output is correct
6 Correct 215 ms 39732 KB Output is correct
7 Correct 65 ms 78528 KB Output is correct
8 Correct 158 ms 39704 KB Output is correct
9 Correct 224 ms 78788 KB Output is correct
10 Correct 226 ms 78816 KB Output is correct
11 Correct 248 ms 78704 KB Output is correct
12 Correct 390 ms 79080 KB Output is correct
13 Correct 415 ms 78900 KB Output is correct
14 Correct 293 ms 78664 KB Output is correct
15 Correct 284 ms 78628 KB Output is correct
16 Correct 394 ms 40076 KB Output is correct
17 Correct 427 ms 78808 KB Output is correct
18 Correct 422 ms 78788 KB Output is correct
19 Correct 388 ms 39932 KB Output is correct
20 Correct 423 ms 79028 KB Output is correct
21 Correct 990 ms 40984 KB Output is correct
22 Correct 1569 ms 41852 KB Output is correct
23 Correct 1959 ms 42904 KB Output is correct
24 Correct 1659 ms 78868 KB Output is correct
25 Correct 340 ms 78852 KB Output is correct
26 Correct 2473 ms 78936 KB Output is correct
27 Correct 3164 ms 43796 KB Output is correct
28 Correct 3117 ms 78916 KB Output is correct
29 Correct 1172 ms 78984 KB Output is correct
30 Correct 3735 ms 44692 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39380 KB Output is correct
2 Correct 185 ms 78704 KB Output is correct
3 Correct 233 ms 78640 KB Output is correct
4 Correct 57 ms 39476 KB Output is correct
5 Correct 132 ms 39592 KB Output is correct
6 Correct 215 ms 39732 KB Output is correct
7 Correct 65 ms 78528 KB Output is correct
8 Correct 158 ms 39704 KB Output is correct
9 Correct 224 ms 78788 KB Output is correct
10 Correct 226 ms 78816 KB Output is correct
11 Execution timed out 4053 ms 45332 KB Time limit exceeded
12 Halted 0 ms 0 KB -