oj.uz

Submission #568354

# Submission time Handle Problem Language Result Execution time Memory
568354 2022-05-25T09:02:29 Z cheissmart Parachute rings (IOI12_rings) C++14
37 / 100
 1701 ms 126088 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 25 ms 47280 KB Output is correct
2 Correct 27 ms 47572 KB Output is correct
3 Correct 42 ms 47692 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 37 ms 47572 KB Output is correct
6 Correct 34 ms 47672 KB Output is correct
7 Correct 26 ms 47360 KB Output is correct
8 Correct 28 ms 47568 KB Output is correct
9 Correct 40 ms 47688 KB Output is correct
10 Correct 39 ms 47692 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 89116 KB Output is correct
2 Correct 1350 ms 107764 KB Output is correct
3 Correct 1590 ms 115036 KB Output is correct
4 Correct 1701 ms 126088 KB Output is correct
5 Correct 1568 ms 125972 KB Output is correct
6 Correct 1490 ms 123912 KB Output is correct
7 Correct 1364 ms 113572 KB Output is correct
8 Correct 1447 ms 117260 KB Output is correct
9 Correct 1550 ms 123948 KB Output is correct
10 Correct 1062 ms 118528 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47280 KB Output is correct
2 Correct 27 ms 47572 KB Output is correct
3 Correct 42 ms 47692 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 37 ms 47572 KB Output is correct
6 Correct 34 ms 47672 KB Output is correct
7 Correct 26 ms 47360 KB Output is correct
8 Correct 28 ms 47568 KB Output is correct
9 Correct 40 ms 47688 KB Output is correct
10 Correct 39 ms 47692 KB Output is correct
11 Incorrect 35 ms 47736 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47280 KB Output is correct
2 Correct 27 ms 47572 KB Output is correct
3 Correct 42 ms 47692 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 37 ms 47572 KB Output is correct
6 Correct 34 ms 47672 KB Output is correct
7 Correct 26 ms 47360 KB Output is correct
8 Correct 28 ms 47568 KB Output is correct
9 Correct 40 ms 47688 KB Output is correct
10 Correct 39 ms 47692 KB Output is correct
11 Incorrect 35 ms 47736 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47280 KB Output is correct
2 Correct 27 ms 47572 KB Output is correct
3 Correct 42 ms 47692 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 37 ms 47572 KB Output is correct
6 Correct 34 ms 47672 KB Output is correct
7 Correct 26 ms 47360 KB Output is correct
8 Correct 28 ms 47568 KB Output is correct
9 Correct 40 ms 47688 KB Output is correct
10 Correct 39 ms 47692 KB Output is correct
11 Correct 801 ms 89116 KB Output is correct
12 Correct 1350 ms 107764 KB Output is correct
13 Correct 1590 ms 115036 KB Output is correct
14 Correct 1701 ms 126088 KB Output is correct
15 Correct 1568 ms 125972 KB Output is correct
16 Correct 1490 ms 123912 KB Output is correct
17 Correct 1364 ms 113572 KB Output is correct
18 Correct 1447 ms 117260 KB Output is correct
19 Correct 1550 ms 123948 KB Output is correct
20 Correct 1062 ms 118528 KB Output is correct
21 Incorrect 35 ms 47736 KB Output isn't correct
22 Halted 0 ms 0 KB -