oj.uz

Submission #568347

# Submission time Handle Problem Language Result Execution time Memory
568347 2022-05-25T08:57:27 Z cheissmart Parachute rings (IOI12_rings) C++14
0 / 100
 1338 ms 254052 KB 
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7, N = 1e6 + 7;
 
int n;
int p[N], sz[N], esz[N];
bool not_in[N];
vi G[N], g[N], s;
 
void Init(int _n) {
    n = _n;
    for(int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
        s.PB(i);
    }
}
 
int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}
 
void unite(int u, int v) {
    u = find(u), v = find(v);
    assert(u != v);
    if(sz[u] > sz[v]) swap(u, v);
    p[u] = v;
    sz[v] += sz[u];
    esz[v] += esz[u];
}
 
V<pi> tt;
int cc = 0, bad_cnt = 0;
 
void inter(vi ss) {
    vi tmp;
    for(int u:s) if(find(ALL(ss), u) != ss.end())
        tmp.PB(u);
    swap(tmp, s);
}
 
void check(int u) {
    if(SZ(g[u]) <= 2) return;
    bad_cnt++;
    if(SZ(g[u]) > 3)
        inter({u});
    inter({u, g[u][0], g[u][1], g[u][2]});
}
 
void Link(int u, int v) {
    if(find(u) != find(v)) {
        if(esz[find(u)] >= sz[find(u)]) cc--;
        if(esz[find(v)] >= sz[find(v)]) cc--;
        unite(u, v);
        esz[find(u)]++;
        if(esz[find(u)] >= sz[find(u)]) cc++;
        G[u].PB(v);
        G[v].PB(u);
    } else {
        if(esz[find(u)] >= sz[find(u)]) cc--;
        esz[find(u)]++;
        if(esz[find(u)] >= sz[find(u)]) cc++;
 
        tt.EB(u, v);
        // if(SZ(tt) <= 2) {
        //     vi stk;
        //     function<void(int, int)> dfs = [&] (int x, int pa) {
        //         stk.PB(x);
        //         if(x == v) {
        //             V<bool> vis(n);
        //             for(int i:stk) vis[i] = true;
        //             for(int i = 0; i < n; i++) if(!vis[i])
        //                 not_in[i] = true;
        //         }
        //         for(int y:g[x]) if(y != pa) {
        //             dfs(y, x);
        //         }
        //         stk.pop_back();
        //     };
        // } 
    }
    g[u].PB(v);
    g[v].PB(u);
    check(u), check(v);
}
 
bool ok(int u) {
    // if(SZ(tt) > 2) return false;
    // if(not_in[u]) return false;
    // return true;
    V<bool> vis(n);
    bool has_cycle = false;
    function<void(int, int)> dfs = [&] (int x, int pa) {
        vis[x] = true;
        for(int y:g[x]) if(y != pa && y != u) {
            if(vis[y]) has_cycle = true;
            else dfs(y, x);
        }
    };
    for(int i = 0; i < n; i++) if(!vis[i] && i != u)
        dfs(i, -1);
    return !has_cycle;
}
 
int CountCritical() {
    if(cc > 1) return 0;
    if(s.empty()) return 0;
    if(cc == 0) return SZ(s);
    // if(esz[find(s[0])] < sz[find(s[0])]) return 0;
    // if(bad_cnt == 1) {
    //     if(SZ(s) == 1) return 1;
    //     return 3;
    // }
    int ans = 0;
    for(int u:s) {
        if(esz[find(u)] < sz[find(u)]) continue;
        assert(find(u) == find(s[0]));
        if(ok(u)) ans++;
    }
    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 31 ms 47552 KB Output is correct
3 Correct 28 ms 47648 KB Output is correct
4 Runtime error 61 ms 95820 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 88072 KB Output is correct
2 Correct 1206 ms 106720 KB Output is correct
3 Correct 1338 ms 114048 KB Output is correct
4 Runtime error 1310 ms 254052 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 31 ms 47552 KB Output is correct
3 Correct 28 ms 47648 KB Output is correct
4 Runtime error 61 ms 95820 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 31 ms 47552 KB Output is correct
3 Correct 28 ms 47648 KB Output is correct
4 Runtime error 61 ms 95820 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47316 KB Output is correct
2 Correct 31 ms 47552 KB Output is correct
3 Correct 28 ms 47648 KB Output is correct
4 Runtime error 61 ms 95820 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -