oj.uz

Submission #568346

# Submission time Handle Problem Language Result Execution time Memory
568346 2022-05-25T08:56:30 Z cheissmart Parachute rings (IOI12_rings) C++14
38 / 100
 4000 ms 126212 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;
        if(ok(u)) ans++;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47188 KB Output is correct
2 Correct 30 ms 47628 KB Output is correct
3 Correct 32 ms 47688 KB Output is correct
4 Correct 25 ms 47296 KB Output is correct
5 Correct 145 ms 47664 KB Output is correct
6 Correct 589 ms 47992 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 26 ms 47560 KB Output is correct
9 Correct 26 ms 47700 KB Output is correct
10 Correct 26 ms 47636 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 87996 KB Output is correct
2 Correct 1251 ms 106780 KB Output is correct
3 Correct 1420 ms 114112 KB Output is correct
4 Execution timed out 4089 ms 126212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47188 KB Output is correct
2 Correct 30 ms 47628 KB Output is correct
3 Correct 32 ms 47688 KB Output is correct
4 Correct 25 ms 47296 KB Output is correct
5 Correct 145 ms 47664 KB Output is correct
6 Correct 589 ms 47992 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 26 ms 47560 KB Output is correct
9 Correct 26 ms 47700 KB Output is correct
10 Correct 26 ms 47636 KB Output is correct
11 Correct 31 ms 47692 KB Output is correct
12 Correct 90 ms 48076 KB Output is correct
13 Correct 40 ms 48132 KB Output is correct
14 Correct 40 ms 47828 KB Output is correct
15 Correct 52 ms 47868 KB Output is correct
16 Correct 174 ms 48200 KB Output is correct
17 Correct 33 ms 48120 KB Output is correct
18 Correct 34 ms 48456 KB Output is correct
19 Correct 141 ms 48248 KB Output is correct
20 Correct 29 ms 48164 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47188 KB Output is correct
2 Correct 30 ms 47628 KB Output is correct
3 Correct 32 ms 47688 KB Output is correct
4 Correct 25 ms 47296 KB Output is correct
5 Correct 145 ms 47664 KB Output is correct
6 Correct 589 ms 47992 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 26 ms 47560 KB Output is correct
9 Correct 26 ms 47700 KB Output is correct
10 Correct 26 ms 47636 KB Output is correct
11 Correct 31 ms 47692 KB Output is correct
12 Correct 90 ms 48076 KB Output is correct
13 Correct 40 ms 48132 KB Output is correct
14 Correct 40 ms 47828 KB Output is correct
15 Correct 52 ms 47868 KB Output is correct
16 Correct 174 ms 48200 KB Output is correct
17 Correct 33 ms 48120 KB Output is correct
18 Correct 34 ms 48456 KB Output is correct
19 Correct 141 ms 48248 KB Output is correct
20 Correct 29 ms 48164 KB Output is correct
21 Correct 42 ms 50296 KB Output is correct
22 Correct 66 ms 51940 KB Output is correct
23 Correct 79 ms 53404 KB Output is correct
24 Execution timed out 4037 ms 50056 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 47188 KB Output is correct
2 Correct 30 ms 47628 KB Output is correct
3 Correct 32 ms 47688 KB Output is correct
4 Correct 25 ms 47296 KB Output is correct
5 Correct 145 ms 47664 KB Output is correct
6 Correct 589 ms 47992 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 26 ms 47560 KB Output is correct
9 Correct 26 ms 47700 KB Output is correct
10 Correct 26 ms 47636 KB Output is correct
11 Correct 626 ms 87996 KB Output is correct
12 Correct 1251 ms 106780 KB Output is correct
13 Correct 1420 ms 114112 KB Output is correct
14 Execution timed out 4089 ms 126212 KB Time limit exceeded
15 Halted 0 ms 0 KB -