oj.uz

Submission #481691

# Submission time Handle Problem Language Result Execution time Memory
481691 2021-10-21T11:12:47 Z Haruto810198 Parachute rings (IOI12_rings) C++17
52 / 100
 1874 ms 262148 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){
        if(u > v) swap(u, v);
        edge[u].pb(v);
        //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);

        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(uu, 0, n-1, 1){
                for(int vv : G_now.edge[uu]){
                    if(vv == u) check_id.pb(uu);
                }
            }

            assert(szof(check_id) == 4);

            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]) continue;
                        G_check[i].add_edge(uu, vv);
                    }
                }
            }

            G_now.init();
            G_now.deg3 = 1;
        }

        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);
            }
        }
    }

}

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 52 ms 117828 KB Output is correct
2 Correct 54 ms 118484 KB Output is correct
3 Correct 55 ms 118476 KB Output is correct
4 Correct 51 ms 117760 KB Output is correct
5 Correct 52 ms 117832 KB Output is correct
6 Correct 53 ms 117912 KB Output is correct
7 Correct 55 ms 118088 KB Output is correct
8 Correct 52 ms 117868 KB Output is correct
9 Correct 57 ms 118596 KB Output is correct
10 Correct 55 ms 118628 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 134740 KB Output is correct
2 Correct 1535 ms 238932 KB Output is correct
3 Correct 1874 ms 245996 KB Output is correct
4 Correct 696 ms 150272 KB Output is correct
5 Correct 682 ms 150420 KB Output is correct
6 Correct 668 ms 149516 KB Output is correct
7 Correct 1796 ms 244448 KB Output is correct
8 Runtime error 1346 ms 262148 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 117828 KB Output is correct
2 Correct 54 ms 118484 KB Output is correct
3 Correct 55 ms 118476 KB Output is correct
4 Correct 51 ms 117760 KB Output is correct
5 Correct 52 ms 117832 KB Output is correct
6 Correct 53 ms 117912 KB Output is correct
7 Correct 55 ms 118088 KB Output is correct
8 Correct 52 ms 117868 KB Output is correct
9 Correct 57 ms 118596 KB Output is correct
10 Correct 55 ms 118628 KB Output is correct
11 Correct 55 ms 118584 KB Output is correct
12 Correct 64 ms 119368 KB Output is correct
13 Correct 59 ms 119276 KB Output is correct
14 Correct 56 ms 118856 KB Output is correct
15 Correct 56 ms 119364 KB Output is correct
16 Correct 56 ms 118128 KB Output is correct
17 Correct 59 ms 119236 KB Output is correct
18 Correct 63 ms 119868 KB Output is correct
19 Correct 55 ms 118084 KB Output is correct
20 Correct 59 ms 119332 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 117828 KB Output is correct
2 Correct 54 ms 118484 KB Output is correct
3 Correct 55 ms 118476 KB Output is correct
4 Correct 51 ms 117760 KB Output is correct
5 Correct 52 ms 117832 KB Output is correct
6 Correct 53 ms 117912 KB Output is correct
7 Correct 55 ms 118088 KB Output is correct
8 Correct 52 ms 117868 KB Output is correct
9 Correct 57 ms 118596 KB Output is correct
10 Correct 55 ms 118628 KB Output is correct
11 Correct 55 ms 118584 KB Output is correct
12 Correct 64 ms 119368 KB Output is correct
13 Correct 59 ms 119276 KB Output is correct
14 Correct 56 ms 118856 KB Output is correct
15 Correct 56 ms 119364 KB Output is correct
16 Correct 56 ms 118128 KB Output is correct
17 Correct 59 ms 119236 KB Output is correct
18 Correct 63 ms 119868 KB Output is correct
19 Correct 55 ms 118084 KB Output is correct
20 Correct 59 ms 119332 KB Output is correct
21 Correct 65 ms 119076 KB Output is correct
22 Correct 81 ms 119788 KB Output is correct
23 Correct 84 ms 120388 KB Output is correct
24 Correct 134 ms 127356 KB Output is correct
25 Correct 71 ms 124232 KB Output is correct
26 Correct 123 ms 128836 KB Output is correct
27 Correct 78 ms 120576 KB Output is correct
28 Correct 145 ms 130444 KB Output is correct
29 Correct 104 ms 127036 KB Output is correct
30 Correct 91 ms 121024 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 117828 KB Output is correct
2 Correct 54 ms 118484 KB Output is correct
3 Correct 55 ms 118476 KB Output is correct
4 Correct 51 ms 117760 KB Output is correct
5 Correct 52 ms 117832 KB Output is correct
6 Correct 53 ms 117912 KB Output is correct
7 Correct 55 ms 118088 KB Output is correct
8 Correct 52 ms 117868 KB Output is correct
9 Correct 57 ms 118596 KB Output is correct
10 Correct 55 ms 118628 KB Output is correct
11 Correct 311 ms 134740 KB Output is correct
12 Correct 1535 ms 238932 KB Output is correct
13 Correct 1874 ms 245996 KB Output is correct
14 Correct 696 ms 150272 KB Output is correct
15 Correct 682 ms 150420 KB Output is correct
16 Correct 668 ms 149516 KB Output is correct
17 Correct 1796 ms 244448 KB Output is correct
18 Runtime error 1346 ms 262148 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -