oj.uz

Submission #415531

# Submission time Handle Problem Language Result Execution time Memory
415531 2021-06-01T08:10:17 Z Pro_ktmr Parachute rings (IOI12_rings) C++17
100 / 100
 2280 ms 141600 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)

struct UnionFind{
    int N;
    vector<int> par, siz, dig;
    int exc;
    bool ok = true;
    void init(int n, int _exc){
        N = n;
        par = vector<int>(N, -1);
        siz = vector<int>(N, 1);
        exc = _exc;
        dig = vector<int>(N, 0);
    }
    int root(int a){
        if(par[a] == -1) return a;
        return par[a] = root(par[a]);
    }
    int unite(int a, int b){
        if(a == exc || b == exc) return 1;
        dig[a]++; dig[b]++;
        ok &= (dig[a] <= 2 && dig[b] <= 2);
        int ra = root(a), rb = root(b);
        if(ra == rb){
            ok = false;
            return 0;
        }
        if(siz[ra] > siz[rb]){
            par[rb] = ra;
            siz[ra] += siz[rb];
        }
        else{
            par[ra] = rb;
            siz[rb] += siz[ra];
        }
        return 1;
    }
    bool isSame(int a, int b){
        return root(a) == root(b);
    }
    int size(int a){
        return siz[root(a)];
    }
};

int N;
int phase = 2, circle = 0, C = 0;
vector<pair<int,int>> note;
vector<int> e[1000000];
UnionFind base, spec[4], spec4;

void Init(int N_) {
    N = N_;
    base.init(N, -1);
}

void Link(int A, int B) {
    note.pb({A,B});
    e[A].pb(B);
    e[B].pb(A);
    if(phase == 2){
        if(e[A].size() == 3){
            phase = 3;
            spec[0].init(N, A);
            rep(i, 3) spec[i+1].init(N, e[A][i]);
            rep(i, 4) for(auto [a,b]:note){
                spec[i].unite(a, b);
            }
            return;
        }
        if(e[B].size() == 3){
            phase = 3;
            spec[0].init(N, B);
            rep(i, 3) spec[i+1].init(N, e[B][i]);
            rep(i, 4) for(auto [a,b]:note){
                spec[i].unite(a, b);
            }
            return;
        }
        if(base.unite(A, B) == 0){
            circle++;
            if(circle == 1){
                C = base.size(A);
                return;
            }
        }
    }
    else if(phase == 3){
        if(e[A].size() == 4){
            phase = 4;
            spec4.init(N, A);
            for(auto [a,b]:note){
                spec4.unite(a, b);
            }
            return;
        }
        if(e[B].size() == 4){
            phase = 4;
            spec4.init(N, B);
            for(auto [a,b]:note){
                spec4.unite(a, b);
            }
            return;
        }
        rep(i, 4) spec[i].unite(A, B);
    }
    else{
        spec4.unite(A, B);
    }
}

int CountCritical() {
    if(phase == 2){
        if(circle == 0) return N;
        else if(circle == 1) return C;
        else return 0;
    }
    else if(phase == 3){
        return (int)spec[0].ok + (int)spec[1].ok + (int)spec[2].ok + (int)spec[3].ok;
    }
    else{
        return (int)spec4.ok;
    }
    return -1;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
rings.cpp:70:13: note: in expansion of macro 'rep'
   70 |             rep(i, 3) spec[i+1].init(N, e[A][i]);
      |             ^~~
rings.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
rings.cpp:71:13: note: in expansion of macro 'rep'
   71 |             rep(i, 4) for(auto [a,b]:note){
      |             ^~~
rings.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
rings.cpp:79:13: note: in expansion of macro 'rep'
   79 |             rep(i, 3) spec[i+1].init(N, e[B][i]);
      |             ^~~
rings.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
rings.cpp:80:13: note: in expansion of macro 'rep'
   80 |             rep(i, 4) for(auto [a,b]:note){
      |             ^~~
rings.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
rings.cpp:110:9: note: in expansion of macro 'rep'
  110 |         rep(i, 4) spec[i].unite(A, B);
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 22 ms 24220 KB Output is correct
3 Correct 20 ms 24388 KB Output is correct
4 Correct 20 ms 23756 KB Output is correct
5 Correct 25 ms 24000 KB Output is correct
6 Correct 20 ms 24036 KB Output is correct
7 Correct 23 ms 24036 KB Output is correct
8 Correct 20 ms 23948 KB Output is correct
9 Correct 22 ms 24268 KB Output is correct
10 Correct 26 ms 24332 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 57140 KB Output is correct
2 Correct 1133 ms 122064 KB Output is correct
3 Correct 1135 ms 141600 KB Output is correct
4 Correct 1283 ms 87920 KB Output is correct
5 Correct 1308 ms 88040 KB Output is correct
6 Correct 1429 ms 86240 KB Output is correct
7 Correct 1411 ms 140164 KB Output is correct
8 Correct 2073 ms 127760 KB Output is correct
9 Correct 2280 ms 134964 KB Output is correct
10 Correct 789 ms 85040 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 22 ms 24220 KB Output is correct
3 Correct 20 ms 24388 KB Output is correct
4 Correct 20 ms 23756 KB Output is correct
5 Correct 25 ms 24000 KB Output is correct
6 Correct 20 ms 24036 KB Output is correct
7 Correct 23 ms 24036 KB Output is correct
8 Correct 20 ms 23948 KB Output is correct
9 Correct 22 ms 24268 KB Output is correct
10 Correct 26 ms 24332 KB Output is correct
11 Correct 20 ms 24440 KB Output is correct
12 Correct 19 ms 25036 KB Output is correct
13 Correct 20 ms 24932 KB Output is correct
14 Correct 22 ms 24780 KB Output is correct
15 Correct 18 ms 25412 KB Output is correct
16 Correct 32 ms 24388 KB Output is correct
17 Correct 19 ms 24900 KB Output is correct
18 Correct 26 ms 25812 KB Output is correct
19 Correct 17 ms 24392 KB Output is correct
20 Correct 18 ms 24908 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 22 ms 24220 KB Output is correct
3 Correct 20 ms 24388 KB Output is correct
4 Correct 20 ms 23756 KB Output is correct
5 Correct 25 ms 24000 KB Output is correct
6 Correct 20 ms 24036 KB Output is correct
7 Correct 23 ms 24036 KB Output is correct
8 Correct 20 ms 23948 KB Output is correct
9 Correct 22 ms 24268 KB Output is correct
10 Correct 26 ms 24332 KB Output is correct
11 Correct 20 ms 24440 KB Output is correct
12 Correct 19 ms 25036 KB Output is correct
13 Correct 20 ms 24932 KB Output is correct
14 Correct 22 ms 24780 KB Output is correct
15 Correct 18 ms 25412 KB Output is correct
16 Correct 32 ms 24388 KB Output is correct
17 Correct 19 ms 24900 KB Output is correct
18 Correct 26 ms 25812 KB Output is correct
19 Correct 17 ms 24392 KB Output is correct
20 Correct 18 ms 24908 KB Output is correct
21 Correct 45 ms 25928 KB Output is correct
22 Correct 76 ms 27164 KB Output is correct
23 Correct 61 ms 28220 KB Output is correct
24 Correct 78 ms 33020 KB Output is correct
25 Correct 43 ms 31308 KB Output is correct
26 Correct 73 ms 33980 KB Output is correct
27 Correct 83 ms 29156 KB Output is correct
28 Correct 111 ms 33464 KB Output is correct
29 Correct 66 ms 33212 KB Output is correct
30 Correct 92 ms 29904 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23756 KB Output is correct
2 Correct 22 ms 24220 KB Output is correct
3 Correct 20 ms 24388 KB Output is correct
4 Correct 20 ms 23756 KB Output is correct
5 Correct 25 ms 24000 KB Output is correct
6 Correct 20 ms 24036 KB Output is correct
7 Correct 23 ms 24036 KB Output is correct
8 Correct 20 ms 23948 KB Output is correct
9 Correct 22 ms 24268 KB Output is correct
10 Correct 26 ms 24332 KB Output is correct
11 Correct 602 ms 57140 KB Output is correct
12 Correct 1133 ms 122064 KB Output is correct
13 Correct 1135 ms 141600 KB Output is correct
14 Correct 1283 ms 87920 KB Output is correct
15 Correct 1308 ms 88040 KB Output is correct
16 Correct 1429 ms 86240 KB Output is correct
17 Correct 1411 ms 140164 KB Output is correct
18 Correct 2073 ms 127760 KB Output is correct
19 Correct 2280 ms 134964 KB Output is correct
20 Correct 789 ms 85040 KB Output is correct
21 Correct 20 ms 24440 KB Output is correct
22 Correct 19 ms 25036 KB Output is correct
23 Correct 20 ms 24932 KB Output is correct
24 Correct 22 ms 24780 KB Output is correct
25 Correct 18 ms 25412 KB Output is correct
26 Correct 32 ms 24388 KB Output is correct
27 Correct 19 ms 24900 KB Output is correct
28 Correct 26 ms 25812 KB Output is correct
29 Correct 17 ms 24392 KB Output is correct
30 Correct 18 ms 24908 KB Output is correct
31 Correct 45 ms 25928 KB Output is correct
32 Correct 76 ms 27164 KB Output is correct
33 Correct 61 ms 28220 KB Output is correct
34 Correct 78 ms 33020 KB Output is correct
35 Correct 43 ms 31308 KB Output is correct
36 Correct 73 ms 33980 KB Output is correct
37 Correct 83 ms 29156 KB Output is correct
38 Correct 111 ms 33464 KB Output is correct
39 Correct 66 ms 33212 KB Output is correct
40 Correct 92 ms 29904 KB Output is correct
41 Correct 280 ms 43356 KB Output is correct
42 Correct 955 ms 99184 KB Output is correct
43 Correct 402 ms 96464 KB Output is correct
44 Correct 919 ms 135908 KB Output is correct
45 Correct 1024 ms 129248 KB Output is correct
46 Correct 1027 ms 77888 KB Output is correct
47 Correct 1192 ms 78788 KB Output is correct
48 Correct 716 ms 119640 KB Output is correct
49 Correct 819 ms 77128 KB Output is correct
50 Correct 888 ms 76416 KB Output is correct
51 Correct 315 ms 89380 KB Output is correct
52 Correct 1041 ms 105780 KB Output is correct
53 Correct 722 ms 120116 KB Output is correct
54 Correct 1694 ms 114228 KB Output is correct
55 Correct 1219 ms 132408 KB Output is correct