oj.uz

Submission #481701

# Submission time Handle Problem Language Result Execution time Memory
481701 2021-10-21T11:49:46 Z Haruto810198 Parachute rings (IOI12_rings) C++17
100 / 100
 1539 ms 209520 KB 
#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int MAX = 1000010;

int n;
vi check_id;

struct Graph{
    vi edge[MAX];
    int deg[MAX];
    int p[MAX], sz[MAX];
    int cyc, cyclen, deg3;

    void init(){
        FOR(i, 0, n-1, 1){
            edge[i].clear();
            deg[i] = 0;
            p[i] = i;
            sz[i] = 1;
        }
        cyc = 0;
        cyclen = 0;
        deg3 = 0;
    }

    int findp(int v){
        if(v == p[v]) return v;
        return p[v] = findp(p[v]);
    }

    bool uni(int u, int v){
        int pu = findp(u);
        int pv = findp(v);
        if(pu == pv) return 0;
        if(sz[pu] > sz[pv]){
            p[pv] = pu;
            sz[pu] += sz[pv];
        }
        else{
            p[pu] = pv;
            sz[pv] += sz[pu];
        }
        return 1;
    }

    void add_edge(int u, int v, bool owo){
        if(owo) edge[u].pb(v);
        if(owo) edge[v].pb(u);
        deg[u]++;
        deg[v]++;
        if(deg[u] == 3) deg3++;
        if(deg[v] == 3) deg3++;
        if(!uni(u, v) and deg3 == 0){
            cyc++;
            cyclen = sz[findp(u)];
        }
    }
};

Graph G_now, G_check[4];

void Init(int N){
    n = N;
    G_now.init();
}

void Link(int u, int v){

    if(G_now.deg3 == 0){
        G_now.add_edge(u, v, 1);

        if(G_now.deg3 > 0){
            if(G_now.deg[u] < G_now.deg[v]) swap(u, v);
            check_id = G_now.edge[u];
            check_id.pb(u);

            FOR(i, 0, 3, 1){
                G_check[i].init();
                FOR(uu, 0, n-1, 1){
                    if(uu == check_id[i]) continue;
                    for(int vv : G_now.edge[uu]){
                        if(vv == check_id[i] or uu < vv) continue;
                        G_check[i].add_edge(uu, vv, 0);

                    }
                }
            }
        }

        return;
    }

    if(G_now.deg3 > 0){
        FOR(i, 0, 3, 1){
            if(u != check_id[i] and v != check_id[i]){
                G_check[i].add_edge(u, v, 0);
            }
        }
    }

}

int CountCritical(){
    if(G_now.deg3 == 0){
        if(G_now.cyc == 0) return n;
        else if(G_now.cyc == 1) return G_now.cyclen;
        else return 0;
    }
    else{
        int ret = 0;
        FOR(i, 0, 3, 1){
            if(G_check[i].cyc == 0 and G_check[i].deg3 == 0) ret++;
        }
        return ret;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117700 KB Output is correct
2 Correct 59 ms 118148 KB Output is correct
3 Correct 58 ms 118176 KB Output is correct
4 Correct 58 ms 117688 KB Output is correct
5 Correct 57 ms 117812 KB Output is correct
6 Correct 56 ms 117888 KB Output is correct
7 Correct 59 ms 118088 KB Output is correct
8 Correct 56 ms 117892 KB Output is correct
9 Correct 57 ms 118184 KB Output is correct
10 Correct 57 ms 118136 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 140192 KB Output is correct
2 Correct 1033 ms 178676 KB Output is correct
3 Correct 945 ms 176848 KB Output is correct
4 Correct 966 ms 160820 KB Output is correct
5 Correct 978 ms 160836 KB Output is correct
6 Correct 955 ms 159704 KB Output is correct
7 Correct 954 ms 177072 KB Output is correct
8 Correct 1375 ms 201728 KB Output is correct
9 Correct 1539 ms 209520 KB Output is correct
10 Correct 647 ms 161652 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117700 KB Output is correct
2 Correct 59 ms 118148 KB Output is correct
3 Correct 58 ms 118176 KB Output is correct
4 Correct 58 ms 117688 KB Output is correct
5 Correct 57 ms 117812 KB Output is correct
6 Correct 56 ms 117888 KB Output is correct
7 Correct 59 ms 118088 KB Output is correct
8 Correct 56 ms 117892 KB Output is correct
9 Correct 57 ms 118184 KB Output is correct
10 Correct 57 ms 118136 KB Output is correct
11 Correct 59 ms 118116 KB Output is correct
12 Correct 59 ms 118724 KB Output is correct
13 Correct 64 ms 118596 KB Output is correct
14 Correct 58 ms 118420 KB Output is correct
15 Correct 58 ms 118988 KB Output is correct
16 Correct 59 ms 118176 KB Output is correct
17 Correct 60 ms 118368 KB Output is correct
18 Correct 60 ms 119028 KB Output is correct
19 Correct 59 ms 118244 KB Output is correct
20 Correct 60 ms 118644 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117700 KB Output is correct
2 Correct 59 ms 118148 KB Output is correct
3 Correct 58 ms 118176 KB Output is correct
4 Correct 58 ms 117688 KB Output is correct
5 Correct 57 ms 117812 KB Output is correct
6 Correct 56 ms 117888 KB Output is correct
7 Correct 59 ms 118088 KB Output is correct
8 Correct 56 ms 117892 KB Output is correct
9 Correct 57 ms 118184 KB Output is correct
10 Correct 57 ms 118136 KB Output is correct
11 Correct 59 ms 118116 KB Output is correct
12 Correct 59 ms 118724 KB Output is correct
13 Correct 64 ms 118596 KB Output is correct
14 Correct 58 ms 118420 KB Output is correct
15 Correct 58 ms 118988 KB Output is correct
16 Correct 59 ms 118176 KB Output is correct
17 Correct 60 ms 118368 KB Output is correct
18 Correct 60 ms 119028 KB Output is correct
19 Correct 59 ms 118244 KB Output is correct
20 Correct 60 ms 118644 KB Output is correct
21 Correct 71 ms 119348 KB Output is correct
22 Correct 79 ms 120292 KB Output is correct
23 Correct 84 ms 120964 KB Output is correct
24 Correct 88 ms 123376 KB Output is correct
25 Correct 70 ms 123780 KB Output is correct
26 Correct 102 ms 123588 KB Output is correct
27 Correct 88 ms 121540 KB Output is correct
28 Correct 85 ms 123076 KB Output is correct
29 Correct 83 ms 124128 KB Output is correct
30 Correct 96 ms 122048 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117700 KB Output is correct
2 Correct 59 ms 118148 KB Output is correct
3 Correct 58 ms 118176 KB Output is correct
4 Correct 58 ms 117688 KB Output is correct
5 Correct 57 ms 117812 KB Output is correct
6 Correct 56 ms 117888 KB Output is correct
7 Correct 59 ms 118088 KB Output is correct
8 Correct 56 ms 117892 KB Output is correct
9 Correct 57 ms 118184 KB Output is correct
10 Correct 57 ms 118136 KB Output is correct
11 Correct 380 ms 140192 KB Output is correct
12 Correct 1033 ms 178676 KB Output is correct
13 Correct 945 ms 176848 KB Output is correct
14 Correct 966 ms 160820 KB Output is correct
15 Correct 978 ms 160836 KB Output is correct
16 Correct 955 ms 159704 KB Output is correct
17 Correct 954 ms 177072 KB Output is correct
18 Correct 1375 ms 201728 KB Output is correct
19 Correct 1539 ms 209520 KB Output is correct
20 Correct 647 ms 161652 KB Output is correct
21 Correct 59 ms 118116 KB Output is correct
22 Correct 59 ms 118724 KB Output is correct
23 Correct 64 ms 118596 KB Output is correct
24 Correct 58 ms 118420 KB Output is correct
25 Correct 58 ms 118988 KB Output is correct
26 Correct 59 ms 118176 KB Output is correct
27 Correct 60 ms 118368 KB Output is correct
28 Correct 60 ms 119028 KB Output is correct
29 Correct 59 ms 118244 KB Output is correct
30 Correct 60 ms 118644 KB Output is correct
31 Correct 71 ms 119348 KB Output is correct
32 Correct 79 ms 120292 KB Output is correct
33 Correct 84 ms 120964 KB Output is correct
34 Correct 88 ms 123376 KB Output is correct
35 Correct 70 ms 123780 KB Output is correct
36 Correct 102 ms 123588 KB Output is correct
37 Correct 88 ms 121540 KB Output is correct
38 Correct 85 ms 123076 KB Output is correct
39 Correct 83 ms 124128 KB Output is correct
40 Correct 96 ms 122048 KB Output is correct
41 Correct 236 ms 135768 KB Output is correct
42 Correct 642 ms 186432 KB Output is correct
43 Correct 302 ms 177220 KB Output is correct
44 Correct 662 ms 184420 KB Output is correct
45 Correct 705 ms 187088 KB Output is correct
46 Correct 615 ms 165516 KB Output is correct
47 Correct 842 ms 166328 KB Output is correct
48 Correct 507 ms 184884 KB Output is correct
49 Correct 616 ms 165440 KB Output is correct
50 Correct 668 ms 164928 KB Output is correct
51 Correct 318 ms 169260 KB Output is correct
52 Correct 565 ms 171848 KB Output is correct
53 Correct 496 ms 183864 KB Output is correct
54 Correct 1130 ms 195636 KB Output is correct
55 Correct 960 ms 182032 KB Output is correct