oj.uz

Submission #286511

# Submission time Handle Problem Language Result Execution time Memory
286511 2020-08-30T13:55:45 Z PeppaPig Parachute rings (IOI12_rings) C++14
0 / 100
 1314 ms 123476 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e6 + 5;

struct UnionFind {
    bool bad = false;
    int cyc_sz = 0, cyc_cnt = 0, cand = -1, all;
    int par[N], end[N], sz[N], cyc[N];

    UnionFind() {}

    void reset() {
        iota(par, par + N, 0);
        iota(end, end + N, 0);
        fill_n(sz, N, 1);
    }

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

    void add_edge(int a, int b) {
        if(bad || a == cand || b == cand) return;
        if(cyc[find(a)] || cyc[find(b)]) {
            bad = true;
            return;
        }
        if(find(a) == find(b)) {
            if(cyc[find(a)]) bad = true;
            else {
                cyc[find(a)] = 1;
                cyc_sz += sz[find(a)];
                ++cyc_cnt;
                if(cyc_cnt > 1) bad = true;
            }
            return;
        }
        if((a != find(a) && a != end[find(a)]) || (b != find(b) && b != end[find(b)])) {
            bad = true;
            return;
        }
        if(a == find(a) && b == find(b)) {
            par[a] = end[a], par[end[a]] = end[a];
            par[b] = find(a), end[find(a)] = end[b], sz[find(a)] += sz[b];
        } else if(a == end[find(a)] && b == end[find(b)])
            end[find(b)] = find(a), par[find(a)] = find(b), sz[find(b)] += sz[find(a)];
        else if(a == find(a) && b == end[find(b)])
            par[a] = find(b), end[find(b)] = end[a], sz[find(b)] += sz[a];
        else if(a == end[find(a)] && b == find(b))
            par[b] = find(a), end[find(a)] = end[b], sz[find(a)] += sz[b];
    }

    int count() {
        if(bad) return 0;
        if(cyc_cnt) return cyc_sz;
        return all;
    }
} dsu[4];

int n;
bool found;
vector<pii> E;
vector<int> g[N];

void Init(int _n) {
    n = _n;
    for(int i = 0; i < 4; i++) {
        dsu[i].reset();
        dsu[i].all = n;
    }
}

void Link(int a, int b) {
    E.emplace_back(a, b);
    g[a].emplace_back(b), g[b].emplace_back(a);
    if(!found) {
        if((int)g[a].size() < 3 && (int)g[b].size() < 3)
            dsu[0].add_edge(a, b);
        else {
            found = true;
            int candid = (int)g[a].size() == 3 ? a : b;
            vector<int> ret = {candid};
            for(int v : g[candid]) ret.emplace_back(v);
            for(int i = 0; i < 4; i++) {
                dsu[i].reset();
                dsu[i].cand = ret[i];
            }
            for(pii e : E) for(int i = 0; i < 4; i++)
                dsu[i].add_edge(e.x, e.y);
        }
    } else for(int i = 0; i < 4; i++)
        dsu[i].add_edge(a, b);
}

int CountCritical() {
    if(found) {
        int ans = 0;
        for(int i = 0; i < 4; i++) if(dsu[i].count() && !dsu[i].cyc_cnt)
            ++ans;
        return ans;
    } else return dsu[0].count();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 51 ms 71040 KB Output is correct
3 Correct 51 ms 71064 KB Output is correct
4 Incorrect 40 ms 70904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 98104 KB Output is correct
2 Correct 1254 ms 112876 KB Output is correct
3 Correct 898 ms 118096 KB Output is correct
4 Incorrect 1314 ms 123476 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 51 ms 71040 KB Output is correct
3 Correct 51 ms 71064 KB Output is correct
4 Incorrect 40 ms 70904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 51 ms 71040 KB Output is correct
3 Correct 51 ms 71064 KB Output is correct
4 Incorrect 40 ms 70904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 51 ms 71040 KB Output is correct
3 Correct 51 ms 71064 KB Output is correct
4 Incorrect 40 ms 70904 KB Output isn't correct
5 Halted 0 ms 0 KB -