oj.uz

Submission #568360

# Submission time Handle Problem Language Result Execution time Memory
568360 2022-05-25T09:08:07 Z cheissmart Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 64816 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], 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;
    } 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);
        vi vis(n);
        if(SZ(tt) <= 5) {
            function<void(int)> dfs = [&] (int x) {
                vis[x] = 1;
                if(x == v) {
                    for(int i = 0; i < n; i++) if(!vis[i])
                        not_in[i] = true;
                }
                for(int y:g[x]) if(!vis[y])
                    dfs(y);
                vis[x] = 0;
            };
            dfs(u);
        } 
    }
    g[u].PB(v);
    g[v].PB(u);
    check(u), check(v);
}
 
bool ok(int u) {
    if(SZ(tt) > 5) 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 14 ms 23764 KB Output is correct
2 Correct 16 ms 24020 KB Output is correct
3 Correct 15 ms 24048 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 15 ms 24276 KB Output is correct
7 Correct 15 ms 23860 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24040 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 48188 KB Output is correct
2 Correct 795 ms 58224 KB Output is correct
3 Execution timed out 4069 ms 64816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 24020 KB Output is correct
3 Correct 15 ms 24048 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 15 ms 24276 KB Output is correct
7 Correct 15 ms 23860 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24040 KB Output is correct
11 Correct 13 ms 24044 KB Output is correct
12 Correct 20 ms 24456 KB Output is correct
13 Correct 20 ms 24388 KB Output is correct
14 Incorrect 18 ms 24276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 24020 KB Output is correct
3 Correct 15 ms 24048 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 15 ms 24276 KB Output is correct
7 Correct 15 ms 23860 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24040 KB Output is correct
11 Correct 13 ms 24044 KB Output is correct
12 Correct 20 ms 24456 KB Output is correct
13 Correct 20 ms 24388 KB Output is correct
14 Incorrect 18 ms 24276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 24020 KB Output is correct
3 Correct 15 ms 24048 KB Output is correct
4 Correct 13 ms 23840 KB Output is correct
5 Correct 13 ms 24020 KB Output is correct
6 Correct 15 ms 24276 KB Output is correct
7 Correct 15 ms 23860 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct
9 Correct 14 ms 24020 KB Output is correct
10 Correct 14 ms 24040 KB Output is correct
11 Correct 468 ms 48188 KB Output is correct
12 Correct 795 ms 58224 KB Output is correct
13 Execution timed out 4069 ms 64816 KB Time limit exceeded
14 Halted 0 ms 0 KB -