oj.uz

Submission #736009

# Submission time Handle Problem Language Result Execution time Memory
736009 2023-05-05T06:26:27 Z horiseun Parachute rings (IOI12_rings) C++17
0 / 100
 4000 ms 78900 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]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void merge(int x, int y) {
        if (!vld || x == rt || y == rt) return;
        if (deg[x] == 2 || deg[y] == 2 || same(x, y)) {
            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 (UnionFind1 u : uf) {
            ans += u.vld;
        }
        return ans;
    } else if (cycsz) return cycsz;
    return n;
}

void Link(int a, int b) {
    if (nne) return;
    if (!uf.empty()) {
        for (UnionFind1 u : uf) {
            u.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)];
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39380 KB Output is correct
2 Execution timed out 4059 ms 78900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39380 KB Output is correct
2 Execution timed out 4059 ms 78900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39380 KB Output is correct
2 Execution timed out 4059 ms 78900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39380 KB Output is correct
2 Execution timed out 4059 ms 78900 KB Time limit exceeded
3 Halted 0 ms 0 KB -