oj.uz

Submission #568371

# Submission time Handle Problem Language Result Execution time Memory
568371 2022-05-25T09:30:03 Z cheissmart Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 71892 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;

int answer;

int qry();

void Init(int _n) {
    n = _n;
    for(int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
        s.PB(i);
    }
    answer = qry();
}
 
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]});
    if(answer) answer = qry();
}
 
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;
        if(answer) answer = qry();
    }
    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 qry() {
    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;
}

int CountCritical() {
    return answer;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24024 KB Output is correct
3 Correct 14 ms 24068 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23960 KB Output is correct
6 Correct 17 ms 24020 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 48160 KB Output is correct
2 Correct 748 ms 58216 KB Output is correct
3 Correct 860 ms 62892 KB Output is correct
4 Correct 919 ms 70616 KB Output is correct
5 Correct 935 ms 71892 KB Output is correct
6 Correct 934 ms 70952 KB Output is correct
7 Correct 948 ms 63564 KB Output is correct
8 Correct 887 ms 65720 KB Output is correct
9 Correct 977 ms 70880 KB Output is correct
10 Correct 663 ms 66460 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24024 KB Output is correct
3 Correct 14 ms 24068 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23960 KB Output is correct
6 Correct 17 ms 24020 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 14 ms 24020 KB Output is correct
12 Correct 17 ms 24404 KB Output is correct
13 Correct 19 ms 24376 KB Output is correct
14 Correct 919 ms 24308 KB Output is correct
15 Correct 2045 ms 24424 KB Output is correct
16 Correct 16 ms 24404 KB Output is correct
17 Correct 17 ms 24276 KB Output is correct
18 Correct 18 ms 24536 KB Output is correct
19 Correct 16 ms 24400 KB Output is correct
20 Correct 16 ms 24396 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24024 KB Output is correct
3 Correct 14 ms 24068 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23960 KB Output is correct
6 Correct 17 ms 24020 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 14 ms 24020 KB Output is correct
12 Correct 17 ms 24404 KB Output is correct
13 Correct 19 ms 24376 KB Output is correct
14 Correct 919 ms 24308 KB Output is correct
15 Correct 2045 ms 24424 KB Output is correct
16 Correct 16 ms 24404 KB Output is correct
17 Correct 17 ms 24276 KB Output is correct
18 Correct 18 ms 24536 KB Output is correct
19 Correct 16 ms 24400 KB Output is correct
20 Correct 16 ms 24396 KB Output is correct
21 Correct 31 ms 25972 KB Output is correct
22 Correct 38 ms 27244 KB Output is correct
23 Correct 47 ms 28116 KB Output is correct
24 Execution timed out 4078 ms 26352 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24024 KB Output is correct
3 Correct 14 ms 24068 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23960 KB Output is correct
6 Correct 17 ms 24020 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 15 ms 24064 KB Output is correct
9 Correct 16 ms 24140 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Correct 350 ms 48160 KB Output is correct
12 Correct 748 ms 58216 KB Output is correct
13 Correct 860 ms 62892 KB Output is correct
14 Correct 919 ms 70616 KB Output is correct
15 Correct 935 ms 71892 KB Output is correct
16 Correct 934 ms 70952 KB Output is correct
17 Correct 948 ms 63564 KB Output is correct
18 Correct 887 ms 65720 KB Output is correct
19 Correct 977 ms 70880 KB Output is correct
20 Correct 663 ms 66460 KB Output is correct
21 Correct 14 ms 24020 KB Output is correct
22 Correct 17 ms 24404 KB Output is correct
23 Correct 19 ms 24376 KB Output is correct
24 Correct 919 ms 24308 KB Output is correct
25 Correct 2045 ms 24424 KB Output is correct
26 Correct 16 ms 24404 KB Output is correct
27 Correct 17 ms 24276 KB Output is correct
28 Correct 18 ms 24536 KB Output is correct
29 Correct 16 ms 24400 KB Output is correct
30 Correct 16 ms 24396 KB Output is correct
31 Correct 31 ms 25972 KB Output is correct
32 Correct 38 ms 27244 KB Output is correct
33 Correct 47 ms 28116 KB Output is correct
34 Execution timed out 4078 ms 26352 KB Time limit exceeded
35 Halted 0 ms 0 KB -