oj.uz

Submission #551275

# Submission time Handle Problem Language Result Execution time Memory
551275 2022-04-20T08:08:22 Z elazarkoren Parachute rings (IOI12_rings) C++17
52 / 100
 4000 ms 234884 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 erased_node;
    bool good = true;
    Dsu() {}
    Dsu(int n, int node): 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);
        }
        degs[pb].clear();
    }
    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:110:13: warning: unused variable 'cnt' [-Wunused-variable]
  110 |         int cnt = 0;
      |             ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 18 ms 24896 KB Output is correct
3 Correct 20 ms 25024 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24216 KB Output is correct
6 Correct 20 ms 24532 KB Output is correct
7 Correct 13 ms 24276 KB Output is correct
8 Correct 15 ms 24408 KB Output is correct
9 Correct 30 ms 26580 KB Output is correct
10 Correct 26 ms 26756 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 99236 KB Output is correct
2 Execution timed out 4078 ms 234884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 18 ms 24896 KB Output is correct
3 Correct 20 ms 25024 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24216 KB Output is correct
6 Correct 20 ms 24532 KB Output is correct
7 Correct 13 ms 24276 KB Output is correct
8 Correct 15 ms 24408 KB Output is correct
9 Correct 30 ms 26580 KB Output is correct
10 Correct 26 ms 26756 KB Output is correct
11 Correct 26 ms 26708 KB Output is correct
12 Correct 51 ms 29532 KB Output is correct
13 Correct 51 ms 29508 KB Output is correct
14 Correct 19 ms 26116 KB Output is correct
15 Correct 20 ms 28236 KB Output is correct
16 Correct 24 ms 25296 KB Output is correct
17 Correct 17 ms 25228 KB Output is correct
18 Correct 19 ms 26364 KB Output is correct
19 Correct 21 ms 25300 KB Output is correct
20 Correct 45 ms 29600 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 18 ms 24896 KB Output is correct
3 Correct 20 ms 25024 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24216 KB Output is correct
6 Correct 20 ms 24532 KB Output is correct
7 Correct 13 ms 24276 KB Output is correct
8 Correct 15 ms 24408 KB Output is correct
9 Correct 30 ms 26580 KB Output is correct
10 Correct 26 ms 26756 KB Output is correct
11 Correct 26 ms 26708 KB Output is correct
12 Correct 51 ms 29532 KB Output is correct
13 Correct 51 ms 29508 KB Output is correct
14 Correct 19 ms 26116 KB Output is correct
15 Correct 20 ms 28236 KB Output is correct
16 Correct 24 ms 25296 KB Output is correct
17 Correct 17 ms 25228 KB Output is correct
18 Correct 19 ms 26364 KB Output is correct
19 Correct 21 ms 25300 KB Output is correct
20 Correct 45 ms 29600 KB Output is correct
21 Correct 49 ms 30304 KB Output is correct
22 Correct 73 ms 34252 KB Output is correct
23 Correct 91 ms 36828 KB Output is correct
24 Correct 112 ms 45284 KB Output is correct
25 Correct 95 ms 76740 KB Output is correct
26 Correct 422 ms 76608 KB Output is correct
27 Correct 104 ms 36032 KB Output is correct
28 Correct 603 ms 73984 KB Output is correct
29 Correct 183 ms 78844 KB Output is correct
30 Correct 166 ms 38344 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 18 ms 24896 KB Output is correct
3 Correct 20 ms 25024 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 15 ms 24216 KB Output is correct
6 Correct 20 ms 24532 KB Output is correct
7 Correct 13 ms 24276 KB Output is correct
8 Correct 15 ms 24408 KB Output is correct
9 Correct 30 ms 26580 KB Output is correct
10 Correct 26 ms 26756 KB Output is correct
11 Correct 1287 ms 99236 KB Output is correct
12 Execution timed out 4078 ms 234884 KB Time limit exceeded
13 Halted 0 ms 0 KB -