oj.uz

Submission #551270

# Submission time Handle Problem Language Result Execution time Memory
551270 2022-04-20T08:04:02 Z elazarkoren Parachute rings (IOI12_rings) C++17
0 / 100
 1787 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);
        }
    }
}


bitset<MAX_N> visited;

void Dfs(int node, vi &c) {
    c.push_back(node);
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) Dfs(neighbor, c);
    }
}

bool Good(int node) {
    visited.reset();
    visited[node] = true;
    for (int neighbor : graph[node]) d1.deg[neighbor]--;
    for (int neighbor : graph[node]) {
        vi c;
        Dfs(neighbor, c);
        if (c.size() <= 1) continue;
        int s = 0;
        vi degs;
        for (int v : c) {
            degs.push_back(d1.deg[v]);
            s += d1.deg[v];
        }
        sort(all(degs));
        if (s == 2 * (c.size() - 1) && degs[0] <= 2) continue;
        for (int v : graph[node]) d1.deg[v]++;
        return false;
    }
    for (int neighbor : graph[node]) d1.deg[neighbor]++;
    return true;
}

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;
        if (Good(v)) dsu.push_back(Dsu(n, v));
        if (max_deg <= 3) {
            for (int neighbor : graph[v]) {
                if (Good(neighbor)) dsu.push_back(Dsu(n, neighbor));
            }
        }
        for (auto &d : dsu) {
            for (pii p : edges) {
                d.Add(p.x, p.y);
            }
        }
        return dsu.size();
    }
    changed = true;
    return 0;
}

Compilation message

rings.cpp: In function 'bool Good(int)':
rings.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if (s == 2 * (c.size() - 1) && degs[0] <= 2) continue;
      |             ~~^~~~~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:143:13: warning: unused variable 'cnt' [-Wunused-variable]
  143 |         int cnt = 0;
      |             ^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23708 KB Output is correct
2 Correct 24 ms 25804 KB Output is correct
3 Correct 24 ms 26576 KB Output is correct
4 Correct 15 ms 24020 KB Output is correct
5 Correct 20 ms 24660 KB Output is correct
6 Correct 19 ms 25376 KB Output is correct
7 Correct 15 ms 24404 KB Output is correct
8 Correct 16 ms 24644 KB Output is correct
9 Incorrect 33 ms 30420 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23708 KB Output is correct
2 Correct 24 ms 25804 KB Output is correct
3 Correct 24 ms 26576 KB Output is correct
4 Correct 15 ms 24020 KB Output is correct
5 Correct 20 ms 24660 KB Output is correct
6 Correct 19 ms 25376 KB Output is correct
7 Correct 15 ms 24404 KB Output is correct
8 Correct 16 ms 24644 KB Output is correct
9 Incorrect 33 ms 30420 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23708 KB Output is correct
2 Correct 24 ms 25804 KB Output is correct
3 Correct 24 ms 26576 KB Output is correct
4 Correct 15 ms 24020 KB Output is correct
5 Correct 20 ms 24660 KB Output is correct
6 Correct 19 ms 25376 KB Output is correct
7 Correct 15 ms 24404 KB Output is correct
8 Correct 16 ms 24644 KB Output is correct
9 Incorrect 33 ms 30420 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23708 KB Output is correct
2 Correct 24 ms 25804 KB Output is correct
3 Correct 24 ms 26576 KB Output is correct
4 Correct 15 ms 24020 KB Output is correct
5 Correct 20 ms 24660 KB Output is correct
6 Correct 19 ms 25376 KB Output is correct
7 Correct 15 ms 24404 KB Output is correct
8 Correct 16 ms 24644 KB Output is correct
9 Incorrect 33 ms 30420 KB Output isn't correct
10 Halted 0 ms 0 KB -