oj.uz

Submission #551271

# Submission time Handle Problem Language Result Execution time Memory
551271 2022-04-20T08:04:51 Z elazarkoren Parachute rings (IOI12_rings) C++17
52 / 100
 1784 ms 262144 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;

struct Dsu {
    vi par, sz, deg;
    vector<multiset<pii, greater<pii>>> degs;
    set<int> bad_comps;
    int n, erased_node;
    bool good = true;
    Dsu() {}
    Dsu(int n, int node): n(n), erased_node(node) {
        par.resize(n), sz.resize(n), deg.resize(n);
        degs.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i, sz[i] = 1;
            degs[i].insert({0, i});
        }
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) {
            bad_comps.insert(pa);
            good = false;
            return;
        }
        if (sz[pa] < sz[pb]) swap(pa, pb);
        if (bad_comps.count(pb)) {
            bad_comps.erase(bad_comps.find(pb));
            bad_comps.insert(pa);
            good = false;
        }
        sz[pa] += sz[pb];
        par[pb] = pa;
        for (pii p : degs[pb]) {
            degs[pa].insert(p);
        }
    }
    void Add(int a, int b) {
        if (a == erased_node || b == erased_node) return;
        Union(a, b);
        int pa = Find(a);
        degs[pa].erase(degs[pa].find({deg[a], a}));
        degs[pa].erase(degs[pa].find({deg[b], b}));
        deg[a]++, deg[b]++;
        degs[pa].insert({deg[a], a});
        degs[pa].insert({deg[b], b});
        if (deg[a] > 2 || deg[b] > 2) {
            bad_comps.insert(pa);
            good = false;
        }
    }
};

int n;

Dsu d1;
bool changed = false;

vi graph[MAX_N];

void Init(int N_) {
    n = N_;
    d1 = Dsu(n, -1);
}

vector<Dsu> dsu;
vii edges;

void Link(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
    edges.push_back({a, b});
    if (!changed) {
        d1.Add(a, b);
    } else {
        for (auto &d : dsu) {
            d.Add(a, b);
        }
    }
}

int CountCritical() {
    if (changed) {
        int cnt = 0;
        for (auto &d : dsu) cnt += d.good;
        return cnt;
    }
    if (d1.good) return n;
    if (d1.bad_comps.size() == 1) {
        int node = *d1.bad_comps.begin();
        auto [max_deg, v] = *d1.degs[node].begin();
        if (max_deg == 2) return d1.sz[node];
        changed = true;
        int cnt = 0;
        dsu.push_back(Dsu(n, v));
        if (max_deg <= 3) {
            for (int neighbor : graph[v]) {
                dsu.push_back(Dsu(n, neighbor));
            }
        }
        for (auto &d : dsu) {
            for (pii p : edges) {
                d.Add(p.x, p.y);
            }
        }
        return CountCritical();
    }
    changed = true;
    return 0;
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:109:13: warning: unused variable 'cnt' [-Wunused-variable]
  109 |         int cnt = 0;
      |             ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23716 KB Output is correct
2 Correct 21 ms 25704 KB Output is correct
3 Correct 22 ms 26388 KB Output is correct
4 Correct 13 ms 24040 KB Output is correct
5 Correct 15 ms 24680 KB Output is correct
6 Correct 18 ms 25348 KB Output is correct
7 Correct 12 ms 24276 KB Output is correct
8 Correct 15 ms 24532 KB Output is correct
9 Correct 33 ms 30284 KB Output is correct
10 Correct 31 ms 29328 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1381 ms 123404 KB Output is correct
2 Runtime error 1784 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23716 KB Output is correct
2 Correct 21 ms 25704 KB Output is correct
3 Correct 22 ms 26388 KB Output is correct
4 Correct 13 ms 24040 KB Output is correct
5 Correct 15 ms 24680 KB Output is correct
6 Correct 18 ms 25348 KB Output is correct
7 Correct 12 ms 24276 KB Output is correct
8 Correct 15 ms 24532 KB Output is correct
9 Correct 33 ms 30284 KB Output is correct
10 Correct 31 ms 29328 KB Output is correct
11 Correct 28 ms 28780 KB Output is correct
12 Correct 57 ms 33952 KB Output is correct
13 Correct 62 ms 34164 KB Output is correct
14 Correct 24 ms 26692 KB Output is correct
15 Correct 19 ms 28628 KB Output is correct
16 Correct 21 ms 25808 KB Output is correct
17 Correct 16 ms 25328 KB Output is correct
18 Correct 18 ms 26580 KB Output is correct
19 Correct 21 ms 26344 KB Output is correct
20 Correct 48 ms 34784 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23716 KB Output is correct
2 Correct 21 ms 25704 KB Output is correct
3 Correct 22 ms 26388 KB Output is correct
4 Correct 13 ms 24040 KB Output is correct
5 Correct 15 ms 24680 KB Output is correct
6 Correct 18 ms 25348 KB Output is correct
7 Correct 12 ms 24276 KB Output is correct
8 Correct 15 ms 24532 KB Output is correct
9 Correct 33 ms 30284 KB Output is correct
10 Correct 31 ms 29328 KB Output is correct
11 Correct 28 ms 28780 KB Output is correct
12 Correct 57 ms 33952 KB Output is correct
13 Correct 62 ms 34164 KB Output is correct
14 Correct 24 ms 26692 KB Output is correct
15 Correct 19 ms 28628 KB Output is correct
16 Correct 21 ms 25808 KB Output is correct
17 Correct 16 ms 25328 KB Output is correct
18 Correct 18 ms 26580 KB Output is correct
19 Correct 21 ms 26344 KB Output is correct
20 Correct 48 ms 34784 KB Output is correct
21 Correct 50 ms 31944 KB Output is correct
22 Correct 83 ms 36688 KB Output is correct
23 Correct 104 ms 40028 KB Output is correct
24 Correct 126 ms 51696 KB Output is correct
25 Correct 102 ms 78056 KB Output is correct
26 Correct 398 ms 89728 KB Output is correct
27 Correct 134 ms 40240 KB Output is correct
28 Correct 484 ms 91544 KB Output is correct
29 Correct 190 ms 85696 KB Output is correct
30 Correct 205 ms 52948 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23716 KB Output is correct
2 Correct 21 ms 25704 KB Output is correct
3 Correct 22 ms 26388 KB Output is correct
4 Correct 13 ms 24040 KB Output is correct
5 Correct 15 ms 24680 KB Output is correct
6 Correct 18 ms 25348 KB Output is correct
7 Correct 12 ms 24276 KB Output is correct
8 Correct 15 ms 24532 KB Output is correct
9 Correct 33 ms 30284 KB Output is correct
10 Correct 31 ms 29328 KB Output is correct
11 Correct 1381 ms 123404 KB Output is correct
12 Runtime error 1784 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -