oj.uz

Submission #568350

# Submission time Handle Problem Language Result Execution time Memory
568350 2022-05-25T08:59:28 Z cheissmart Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 128096 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;
 
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++;
        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(intered && 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 33 ms 47224 KB Output is correct
2 Correct 30 ms 47560 KB Output is correct
3 Correct 28 ms 47708 KB Output is correct
4 Correct 49 ms 47376 KB Output is correct
5 Correct 284 ms 47692 KB Output is correct
6 Correct 833 ms 48048 KB Output is correct
7 Correct 30 ms 47368 KB Output is correct
8 Correct 36 ms 47548 KB Output is correct
9 Correct 34 ms 47744 KB Output is correct
10 Correct 36 ms 47700 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 89020 KB Output is correct
2 Correct 1341 ms 107592 KB Output is correct
3 Correct 1726 ms 115648 KB Output is correct
4 Execution timed out 4085 ms 128096 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47224 KB Output is correct
2 Correct 30 ms 47560 KB Output is correct
3 Correct 28 ms 47708 KB Output is correct
4 Correct 49 ms 47376 KB Output is correct
5 Correct 284 ms 47692 KB Output is correct
6 Correct 833 ms 48048 KB Output is correct
7 Correct 30 ms 47368 KB Output is correct
8 Correct 36 ms 47548 KB Output is correct
9 Correct 34 ms 47744 KB Output is correct
10 Correct 36 ms 47700 KB Output is correct
11 Correct 35 ms 47628 KB Output is correct
12 Execution timed out 4067 ms 48196 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47224 KB Output is correct
2 Correct 30 ms 47560 KB Output is correct
3 Correct 28 ms 47708 KB Output is correct
4 Correct 49 ms 47376 KB Output is correct
5 Correct 284 ms 47692 KB Output is correct
6 Correct 833 ms 48048 KB Output is correct
7 Correct 30 ms 47368 KB Output is correct
8 Correct 36 ms 47548 KB Output is correct
9 Correct 34 ms 47744 KB Output is correct
10 Correct 36 ms 47700 KB Output is correct
11 Correct 35 ms 47628 KB Output is correct
12 Execution timed out 4067 ms 48196 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47224 KB Output is correct
2 Correct 30 ms 47560 KB Output is correct
3 Correct 28 ms 47708 KB Output is correct
4 Correct 49 ms 47376 KB Output is correct
5 Correct 284 ms 47692 KB Output is correct
6 Correct 833 ms 48048 KB Output is correct
7 Correct 30 ms 47368 KB Output is correct
8 Correct 36 ms 47548 KB Output is correct
9 Correct 34 ms 47744 KB Output is correct
10 Correct 36 ms 47700 KB Output is correct
11 Correct 764 ms 89020 KB Output is correct
12 Correct 1341 ms 107592 KB Output is correct
13 Correct 1726 ms 115648 KB Output is correct
14 Execution timed out 4085 ms 128096 KB Time limit exceeded
15 Halted 0 ms 0 KB -