oj.uz

Submission #481509

# Submission time Handle Problem Language Result Execution time Memory
481509 2021-10-21T05:17:15 Z Haruto810198 Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 134156 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 edge[MAX];
int deg[MAX];

int p[MAX], sz[MAX];

set<int> check;
int deg3, deg4, cycs, cyclen;

struct DSU{

    int p[MAX], sz[MAX];

    void init(){
        FOR(i, 0, n-1, 1){
            p[i] = i;
            sz[i] = 1;
        }
    }

    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(p[u]);
        int pv = findp(p[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;
    }

};

DSU G_now, G_check;

void Init(int N){
    n = N;
    FOR(i, 0, n-1, 1){
        check.insert(i);
    }
    G_now.init();
}

void upd_check(vi val){
    set<int> ret;
    for(int i : val){
        if(check.find(i) != check.end()) ret.insert(i);
    }
    check = ret;
}

void Link(int u, int v){
    edge[u].pb(v);
    edge[v].pb(u);
    deg[u]++;
    deg[v]++;

    if(deg[u] == 3) deg3++, upd_check({u, edge[u][0], edge[u][1], edge[u][2]});
    if(deg[v] == 3) deg3++, upd_check({v, edge[v][0], edge[v][1], edge[v][2]});
    if(deg[u] == 4) deg3--, deg4++, upd_check({u});
    if(deg[v] == 4) deg3--, deg4++, upd_check({v});

    if(deg3 + deg4 == 0 and G_now.findp(u) == G_now.findp(v)){
        G_now.uni(u, v);
        cycs++;
        cyclen += G_now.sz[G_now.findp(u)];
    }

    G_now.uni(u, v);
}

int CountCritical(){
    if(deg3 + deg4 == 0){
        if(cycs == 0) return n;
        else if(cycs == 1) return cyclen;
        else return 0;
    }
    else{
        int ret = 0;
        for(int v : check){

            bool AC = 1;
            G_check.init();

            FOR(uu, 0, n-1, 1){
                if(uu == v) continue;
                for(int vv : edge[uu]){
                    if(vv == v or uu < vv) continue;
                    if(!G_check.uni(uu, vv)) AC = 0;
                }
            }

            if(AC) ret++;
            //cerr<<"check "<<v<<": "<<AC<<endl;

        }
        return ret;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 14 ms 24268 KB Output is correct
3 Correct 15 ms 24228 KB Output is correct
4 Correct 13 ms 23884 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 17 ms 24348 KB Output is correct
7 Correct 14 ms 24088 KB Output is correct
8 Correct 14 ms 24136 KB Output is correct
9 Correct 14 ms 24308 KB Output is correct
10 Correct 17 ms 24396 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 77492 KB Output is correct
2 Correct 1118 ms 101736 KB Output is correct
3 Correct 1203 ms 95816 KB Output is correct
4 Correct 1241 ms 127160 KB Output is correct
5 Correct 1248 ms 127228 KB Output is correct
6 Correct 1258 ms 125452 KB Output is correct
7 Correct 1173 ms 95196 KB Output is correct
8 Correct 1477 ms 125004 KB Output is correct
9 Correct 1462 ms 134156 KB Output is correct
10 Correct 920 ms 124696 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 14 ms 24268 KB Output is correct
3 Correct 15 ms 24228 KB Output is correct
4 Correct 13 ms 23884 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 17 ms 24348 KB Output is correct
7 Correct 14 ms 24088 KB Output is correct
8 Correct 14 ms 24136 KB Output is correct
9 Correct 14 ms 24308 KB Output is correct
10 Correct 17 ms 24396 KB Output is correct
11 Correct 25 ms 24348 KB Output is correct
12 Correct 23 ms 24916 KB Output is correct
13 Correct 48 ms 24944 KB Output is correct
14 Correct 26 ms 24524 KB Output is correct
15 Correct 35 ms 25288 KB Output is correct
16 Correct 23 ms 24840 KB Output is correct
17 Correct 22 ms 24672 KB Output is correct
18 Correct 20 ms 25100 KB Output is correct
19 Correct 17 ms 24784 KB Output is correct
20 Correct 32 ms 24892 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 14 ms 24268 KB Output is correct
3 Correct 15 ms 24228 KB Output is correct
4 Correct 13 ms 23884 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 17 ms 24348 KB Output is correct
7 Correct 14 ms 24088 KB Output is correct
8 Correct 14 ms 24136 KB Output is correct
9 Correct 14 ms 24308 KB Output is correct
10 Correct 17 ms 24396 KB Output is correct
11 Correct 25 ms 24348 KB Output is correct
12 Correct 23 ms 24916 KB Output is correct
13 Correct 48 ms 24944 KB Output is correct
14 Correct 26 ms 24524 KB Output is correct
15 Correct 35 ms 25288 KB Output is correct
16 Correct 23 ms 24840 KB Output is correct
17 Correct 22 ms 24672 KB Output is correct
18 Correct 20 ms 25100 KB Output is correct
19 Correct 17 ms 24784 KB Output is correct
20 Correct 32 ms 24892 KB Output is correct
21 Correct 35 ms 28144 KB Output is correct
22 Correct 51 ms 30608 KB Output is correct
23 Correct 74 ms 32512 KB Output is correct
24 Execution timed out 4057 ms 30444 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 14 ms 24268 KB Output is correct
3 Correct 15 ms 24228 KB Output is correct
4 Correct 13 ms 23884 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 17 ms 24348 KB Output is correct
7 Correct 14 ms 24088 KB Output is correct
8 Correct 14 ms 24136 KB Output is correct
9 Correct 14 ms 24308 KB Output is correct
10 Correct 17 ms 24396 KB Output is correct
11 Correct 519 ms 77492 KB Output is correct
12 Correct 1118 ms 101736 KB Output is correct
13 Correct 1203 ms 95816 KB Output is correct
14 Correct 1241 ms 127160 KB Output is correct
15 Correct 1248 ms 127228 KB Output is correct
16 Correct 1258 ms 125452 KB Output is correct
17 Correct 1173 ms 95196 KB Output is correct
18 Correct 1477 ms 125004 KB Output is correct
19 Correct 1462 ms 134156 KB Output is correct
20 Correct 920 ms 124696 KB Output is correct
21 Correct 25 ms 24348 KB Output is correct
22 Correct 23 ms 24916 KB Output is correct
23 Correct 48 ms 24944 KB Output is correct
24 Correct 26 ms 24524 KB Output is correct
25 Correct 35 ms 25288 KB Output is correct
26 Correct 23 ms 24840 KB Output is correct
27 Correct 22 ms 24672 KB Output is correct
28 Correct 20 ms 25100 KB Output is correct
29 Correct 17 ms 24784 KB Output is correct
30 Correct 32 ms 24892 KB Output is correct
31 Correct 35 ms 28144 KB Output is correct
32 Correct 51 ms 30608 KB Output is correct
33 Correct 74 ms 32512 KB Output is correct
34 Execution timed out 4057 ms 30444 KB Time limit exceeded
35 Halted 0 ms 0 KB -