oj.uz

Submission #754262

# Submission time Handle Problem Language Result Execution time Memory
754262 2023-06-07T11:17:22 Z lukameladze Parachute rings (IOI12_rings) C++17
100 / 100
 2593 ms 254616 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int MX = 1e6 + 5;
int n, a, b, p[MX], bad_deg[MX],par[4][MX],sz[MX],cnt_cyc = 0,cyc_len = 0, cycles[MX];
int deg_[4][MX], in_deg[MX],can[MX];
vector <int> v[MX], pot;
void Init(int N_) {
    n = N_;
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
}
int get_col(int a) {
    if (a == p[a]) return a;
    else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
    a = get_col(a);
    b = get_col(b);
    if (a == b) {
        cnt_cyc++;
        cyc_len = sz[a];
        return ;
    }
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
    sz[b] = 0;
}

int get_col(int a, int ty) {
    if (a == par[ty][a]) return a;
    else return par[ty][a] = get_col(par[ty][a], ty);
}
void join(int a, int b, int ty) {
    // cout<<"join "<<a<<" "<<get_col(a, ty)<<" "<<b<<" "<<get_col(b, ty)<<" "<<ty<<"\n";
     deg_[ty][a]++; deg_[ty][b]++;
    a = get_col(a, ty);
    b = get_col(b, ty);

    if (a == b) {
    //    cout<<"tyy "<<ty<<"\n";
        cycles[ty]++;
        return ;
    }

    if(deg_[ty][a] > 2 || deg_[ty][b] > 2) bad_deg[ty] = 1;
    par[ty][b] = a;
}

void build(int a, int ty) {
    //cout<<"build  "<<ty<<" "<<a<<"\n";
    for (int i = 1; i <= n; i++) {
        par[ty][i] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int x : v[i]) {
            if (i != a && x != a && i < x) join(i, x, ty);
        }
    }
}
map <int, bool> adj[MX];
void Link(int A, int B) {
    A++; B++;
    a = A; b = B;
    in_deg[a]++; in_deg[b]++;
    adj[a][b] = 1; adj[b][a] = 1;
    v[a].pb(b); v[b].pb(a);
    int ff = 0;
    if (in_deg[a] == 4) {
        assert(pot.size());
        int is_a = 0;
        for (int x : pot) if (x == a) is_a = 1;

        if (is_a == 0) {
            pot.clear(); pot.pb(-1);
            return ;
        } else {
            for (int x : pot) can[x] = 0; can[a] = 1;
        }
    }
    if (in_deg[b] == 4) {
        assert(pot.size());
        int is_b = 0;
        for (int x : pot) if (x == b) is_b = 1;
        if (is_b == 0) {
            pot.clear(); pot.pb(-1);
            return ;
        } else {
            for (int x : pot) can[x] = 0; can[b] = 1;
        }
    }
    if (in_deg[a] == 3 && !pot.size()) {
        pot.pb(a); can[a]  = 1; ff = 1;
        for (int x : v[a]) pot.pb(x),can[x] = 1;
        for (int i = 0; i < pot.size(); i++) build(pot[i], i);
    } else if (in_deg[a] == 3 && pot.size()) {
        for (int x : pot) {
            if (x != a && adj[a][x] != 1) can[x] = 0;
        }
    }

    if (in_deg[b] == 3 && !pot.size()) {
        pot.pb(b); can[b]  = 1; ff = 1;
        for (int x : v[b]) pot.pb(x),can[x] = 1;
        for (int i = 0; i < pot.size(); i++) build(pot[i], i);
    } else if (in_deg[b] == 3 && pot.size()) {
        for (int x : pot) {
            if (x != b && adj[b][x] != 1) can[x] = 0;
        }
    }

    col(a, b);
    if (pot.size() && pot[0] != -1 ) {
        for (int i = 0; i < pot.size(); i++) {
            if (a != pot[i] && b != pot[i] && !ff) join(a, b, i);
        }
    }
}
int CountCritical() {
    if (!pot.size()) {
        if (cnt_cyc > 1) return 0;
        if (cnt_cyc == 0) return n;
        if (cnt_cyc == 1) return cyc_len;
    }
    if (pot.size() && pot[0] == -1) {
        return 0;
    }
    int res = 0;
    for (int i = 0; i < pot.size(); i++) {
       // cout<<cycles[i]<<"       "<<bad_deg[i]<<" "<<can[pot[i]]<<"\n";
        if (!can[pot[i]]) continue;

        if (!cycles[i] && !bad_deg[i]) res++;
    }
    return res;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:81:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   81 |             for (int x : pot) can[x] = 0; can[a] = 1;
      |             ^~~
rings.cpp:81:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |             for (int x : pot) can[x] = 0; can[a] = 1;
      |                                           ^~~
rings.cpp:92:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |             for (int x : pot) can[x] = 0; can[b] = 1;
      |             ^~~
rings.cpp:92:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |             for (int x : pot) can[x] = 0; can[b] = 1;
      |                                           ^~~
rings.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = 0; i < pot.size(); i++) build(pot[i], i);
      |                         ~~^~~~~~~~~~~~
rings.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for (int i = 0; i < pot.size(); i++) build(pot[i], i);
      |                         ~~^~~~~~~~~~~~
rings.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 0; i < pot.size(); i++) {
      |                         ~~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < pot.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70752 KB Output is correct
2 Correct 39 ms 71612 KB Output is correct
3 Correct 40 ms 71700 KB Output is correct
4 Correct 35 ms 70876 KB Output is correct
5 Correct 37 ms 71120 KB Output is correct
6 Correct 45 ms 71532 KB Output is correct
7 Correct 38 ms 71048 KB Output is correct
8 Correct 38 ms 71316 KB Output is correct
9 Correct 39 ms 71692 KB Output is correct
10 Correct 42 ms 71768 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 145320 KB Output is correct
2 Correct 2176 ms 208412 KB Output is correct
3 Correct 1945 ms 254616 KB Output is correct
4 Correct 1770 ms 220732 KB Output is correct
5 Correct 1867 ms 220924 KB Output is correct
6 Correct 1830 ms 216456 KB Output is correct
7 Correct 1756 ms 248836 KB Output is correct
8 Correct 2421 ms 240604 KB Output is correct
9 Correct 2593 ms 252000 KB Output is correct
10 Correct 1326 ms 213196 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70752 KB Output is correct
2 Correct 39 ms 71612 KB Output is correct
3 Correct 40 ms 71700 KB Output is correct
4 Correct 35 ms 70876 KB Output is correct
5 Correct 37 ms 71120 KB Output is correct
6 Correct 45 ms 71532 KB Output is correct
7 Correct 38 ms 71048 KB Output is correct
8 Correct 38 ms 71316 KB Output is correct
9 Correct 39 ms 71692 KB Output is correct
10 Correct 42 ms 71768 KB Output is correct
11 Correct 51 ms 71792 KB Output is correct
12 Correct 49 ms 72608 KB Output is correct
13 Correct 44 ms 72720 KB Output is correct
14 Correct 42 ms 72404 KB Output is correct
15 Correct 46 ms 72840 KB Output is correct
16 Correct 42 ms 72164 KB Output is correct
17 Correct 44 ms 72720 KB Output is correct
18 Correct 49 ms 73232 KB Output is correct
19 Correct 67 ms 72180 KB Output is correct
20 Correct 44 ms 72644 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70752 KB Output is correct
2 Correct 39 ms 71612 KB Output is correct
3 Correct 40 ms 71700 KB Output is correct
4 Correct 35 ms 70876 KB Output is correct
5 Correct 37 ms 71120 KB Output is correct
6 Correct 45 ms 71532 KB Output is correct
7 Correct 38 ms 71048 KB Output is correct
8 Correct 38 ms 71316 KB Output is correct
9 Correct 39 ms 71692 KB Output is correct
10 Correct 42 ms 71768 KB Output is correct
11 Correct 51 ms 71792 KB Output is correct
12 Correct 49 ms 72608 KB Output is correct
13 Correct 44 ms 72720 KB Output is correct
14 Correct 42 ms 72404 KB Output is correct
15 Correct 46 ms 72840 KB Output is correct
16 Correct 42 ms 72164 KB Output is correct
17 Correct 44 ms 72720 KB Output is correct
18 Correct 49 ms 73232 KB Output is correct
19 Correct 67 ms 72180 KB Output is correct
20 Correct 44 ms 72644 KB Output is correct
21 Correct 73 ms 75248 KB Output is correct
22 Correct 78 ms 77748 KB Output is correct
23 Correct 93 ms 79660 KB Output is correct
24 Correct 154 ms 83808 KB Output is correct
25 Correct 63 ms 76756 KB Output is correct
26 Correct 146 ms 84088 KB Output is correct
27 Correct 129 ms 83276 KB Output is correct
28 Correct 137 ms 87008 KB Output is correct
29 Correct 87 ms 80220 KB Output is correct
30 Correct 163 ms 85320 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 70752 KB Output is correct
2 Correct 39 ms 71612 KB Output is correct
3 Correct 40 ms 71700 KB Output is correct
4 Correct 35 ms 70876 KB Output is correct
5 Correct 37 ms 71120 KB Output is correct
6 Correct 45 ms 71532 KB Output is correct
7 Correct 38 ms 71048 KB Output is correct
8 Correct 38 ms 71316 KB Output is correct
9 Correct 39 ms 71692 KB Output is correct
10 Correct 42 ms 71768 KB Output is correct
11 Correct 854 ms 145320 KB Output is correct
12 Correct 2176 ms 208412 KB Output is correct
13 Correct 1945 ms 254616 KB Output is correct
14 Correct 1770 ms 220732 KB Output is correct
15 Correct 1867 ms 220924 KB Output is correct
16 Correct 1830 ms 216456 KB Output is correct
17 Correct 1756 ms 248836 KB Output is correct
18 Correct 2421 ms 240604 KB Output is correct
19 Correct 2593 ms 252000 KB Output is correct
20 Correct 1326 ms 213196 KB Output is correct
21 Correct 51 ms 71792 KB Output is correct
22 Correct 49 ms 72608 KB Output is correct
23 Correct 44 ms 72720 KB Output is correct
24 Correct 42 ms 72404 KB Output is correct
25 Correct 46 ms 72840 KB Output is correct
26 Correct 42 ms 72164 KB Output is correct
27 Correct 44 ms 72720 KB Output is correct
28 Correct 49 ms 73232 KB Output is correct
29 Correct 67 ms 72180 KB Output is correct
30 Correct 44 ms 72644 KB Output is correct
31 Correct 73 ms 75248 KB Output is correct
32 Correct 78 ms 77748 KB Output is correct
33 Correct 93 ms 79660 KB Output is correct
34 Correct 154 ms 83808 KB Output is correct
35 Correct 63 ms 76756 KB Output is correct
36 Correct 146 ms 84088 KB Output is correct
37 Correct 129 ms 83276 KB Output is correct
38 Correct 137 ms 87008 KB Output is correct
39 Correct 87 ms 80220 KB Output is correct
40 Correct 163 ms 85320 KB Output is correct
41 Correct 351 ms 107432 KB Output is correct
42 Correct 1104 ms 170584 KB Output is correct
43 Correct 378 ms 124620 KB Output is correct
44 Correct 1363 ms 234140 KB Output is correct
45 Correct 1265 ms 206048 KB Output is correct
46 Correct 1270 ms 194724 KB Output is correct
47 Correct 1577 ms 197080 KB Output is correct
48 Correct 800 ms 168584 KB Output is correct
49 Correct 1186 ms 184456 KB Output is correct
50 Correct 1228 ms 184068 KB Output is correct
51 Correct 519 ms 125960 KB Output is correct
52 Correct 1446 ms 203572 KB Output is correct
53 Correct 858 ms 172084 KB Output is correct
54 Correct 2234 ms 217212 KB Output is correct
55 Correct 2348 ms 230972 KB Output is correct