oj.uz

Submission #568365

# Submission time Handle Problem Language Result Execution time Memory
568365 2022-05-25T09:14:44 Z cheissmart Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 65384 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) <= 3) {
            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) > 3) 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 12 ms 23820 KB Output is correct
2 Correct 14 ms 23916 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 14 ms 24276 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24020 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 48140 KB Output is correct
2 Correct 713 ms 58220 KB Output is correct
3 Execution timed out 4066 ms 65384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 14 ms 23916 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 14 ms 24276 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24020 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 14 ms 24060 KB Output is correct
12 Correct 19 ms 24392 KB Output is correct
13 Correct 16 ms 24272 KB Output is correct
14 Incorrect 16 ms 24148 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 14 ms 23916 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 14 ms 24276 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24020 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 14 ms 24060 KB Output is correct
12 Correct 19 ms 24392 KB Output is correct
13 Correct 16 ms 24272 KB Output is correct
14 Incorrect 16 ms 24148 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23820 KB Output is correct
2 Correct 14 ms 23916 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 14 ms 23988 KB Output is correct
6 Correct 14 ms 24276 KB Output is correct
7 Correct 12 ms 23884 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24020 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 335 ms 48140 KB Output is correct
12 Correct 713 ms 58220 KB Output is correct
13 Execution timed out 4066 ms 65384 KB Time limit exceeded
14 Halted 0 ms 0 KB -