oj.uz

Submission #568353

# Submission time Handle Problem Language Result Execution time Memory
568353 2022-05-25T09:02:09 Z cheissmart Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 125596 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], intered = false;
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, any_cycle = -1;
 
void inter(vi ss) {
    intered = true;
    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++, any_cycle = u;
        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++, any_cycle = u;
 
        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(!intered) return sz[find(any_cycle)];
    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(ok(u)) ans++;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 31 ms 47644 KB Output is correct
3 Correct 31 ms 47580 KB Output is correct
4 Correct 26 ms 47272 KB Output is correct
5 Correct 31 ms 47452 KB Output is correct
6 Correct 30 ms 47720 KB Output is correct
7 Correct 32 ms 47416 KB Output is correct
8 Correct 29 ms 47552 KB Output is correct
9 Correct 34 ms 47612 KB Output is correct
10 Correct 27 ms 47580 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 87916 KB Output is correct
2 Correct 1264 ms 106704 KB Output is correct
3 Correct 1454 ms 114084 KB Output is correct
4 Correct 1506 ms 125376 KB Output is correct
5 Correct 1541 ms 125596 KB Output is correct
6 Correct 1478 ms 123368 KB Output is correct
7 Correct 1367 ms 112984 KB Output is correct
8 Correct 1499 ms 116996 KB Output is correct
9 Correct 1527 ms 123488 KB Output is correct
10 Correct 997 ms 118112 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 31 ms 47644 KB Output is correct
3 Correct 31 ms 47580 KB Output is correct
4 Correct 26 ms 47272 KB Output is correct
5 Correct 31 ms 47452 KB Output is correct
6 Correct 30 ms 47720 KB Output is correct
7 Correct 32 ms 47416 KB Output is correct
8 Correct 29 ms 47552 KB Output is correct
9 Correct 34 ms 47612 KB Output is correct
10 Correct 27 ms 47580 KB Output is correct
11 Correct 31 ms 47744 KB Output is correct
12 Correct 32 ms 48084 KB Output is correct
13 Correct 38 ms 48080 KB Output is correct
14 Correct 45 ms 47820 KB Output is correct
15 Correct 67 ms 47860 KB Output is correct
16 Correct 40 ms 48084 KB Output is correct
17 Correct 29 ms 47980 KB Output is correct
18 Correct 42 ms 48308 KB Output is correct
19 Correct 39 ms 48076 KB Output is correct
20 Correct 35 ms 48076 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 31 ms 47644 KB Output is correct
3 Correct 31 ms 47580 KB Output is correct
4 Correct 26 ms 47272 KB Output is correct
5 Correct 31 ms 47452 KB Output is correct
6 Correct 30 ms 47720 KB Output is correct
7 Correct 32 ms 47416 KB Output is correct
8 Correct 29 ms 47552 KB Output is correct
9 Correct 34 ms 47612 KB Output is correct
10 Correct 27 ms 47580 KB Output is correct
11 Correct 31 ms 47744 KB Output is correct
12 Correct 32 ms 48084 KB Output is correct
13 Correct 38 ms 48080 KB Output is correct
14 Correct 45 ms 47820 KB Output is correct
15 Correct 67 ms 47860 KB Output is correct
16 Correct 40 ms 48084 KB Output is correct
17 Correct 29 ms 47980 KB Output is correct
18 Correct 42 ms 48308 KB Output is correct
19 Correct 39 ms 48076 KB Output is correct
20 Correct 35 ms 48076 KB Output is correct
21 Correct 59 ms 49948 KB Output is correct
22 Correct 81 ms 51392 KB Output is correct
23 Correct 86 ms 52580 KB Output is correct
24 Execution timed out 4089 ms 49204 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 31 ms 47644 KB Output is correct
3 Correct 31 ms 47580 KB Output is correct
4 Correct 26 ms 47272 KB Output is correct
5 Correct 31 ms 47452 KB Output is correct
6 Correct 30 ms 47720 KB Output is correct
7 Correct 32 ms 47416 KB Output is correct
8 Correct 29 ms 47552 KB Output is correct
9 Correct 34 ms 47612 KB Output is correct
10 Correct 27 ms 47580 KB Output is correct
11 Correct 732 ms 87916 KB Output is correct
12 Correct 1264 ms 106704 KB Output is correct
13 Correct 1454 ms 114084 KB Output is correct
14 Correct 1506 ms 125376 KB Output is correct
15 Correct 1541 ms 125596 KB Output is correct
16 Correct 1478 ms 123368 KB Output is correct
17 Correct 1367 ms 112984 KB Output is correct
18 Correct 1499 ms 116996 KB Output is correct
19 Correct 1527 ms 123488 KB Output is correct
20 Correct 997 ms 118112 KB Output is correct
21 Correct 31 ms 47744 KB Output is correct
22 Correct 32 ms 48084 KB Output is correct
23 Correct 38 ms 48080 KB Output is correct
24 Correct 45 ms 47820 KB Output is correct
25 Correct 67 ms 47860 KB Output is correct
26 Correct 40 ms 48084 KB Output is correct
27 Correct 29 ms 47980 KB Output is correct
28 Correct 42 ms 48308 KB Output is correct
29 Correct 39 ms 48076 KB Output is correct
30 Correct 35 ms 48076 KB Output is correct
31 Correct 59 ms 49948 KB Output is correct
32 Correct 81 ms 51392 KB Output is correct
33 Correct 86 ms 52580 KB Output is correct
34 Execution timed out 4089 ms 49204 KB Time limit exceeded
35 Halted 0 ms 0 KB -