oj.uz

Submission #754238

# Submission time Handle Problem Language Result Execution time Memory
754238 2023-06-07T10:05:46 Z lukameladze Parachute rings (IOI12_rings) C++17
52 / 100
 2057 ms 205356 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[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:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < pot.size(); i++) build(pot[i], i);
      |                         ~~^~~~~~~~~~~~
rings.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int i = 0; i < pot.size(); i++) build(pot[i], i);
      |                         ~~^~~~~~~~~~~~
rings.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int i = 0; i < pot.size(); i++) {
      |                         ~~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < pot.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70744 KB Output is correct
2 Correct 40 ms 71500 KB Output is correct
3 Correct 42 ms 71684 KB Output is correct
4 Correct 38 ms 70824 KB Output is correct
5 Correct 40 ms 71116 KB Output is correct
6 Correct 44 ms 71428 KB Output is correct
7 Correct 37 ms 71048 KB Output is correct
8 Correct 51 ms 71284 KB Output is correct
9 Correct 47 ms 71712 KB Output is correct
10 Correct 54 ms 71712 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 142356 KB Output is correct
2 Incorrect 2057 ms 205356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70744 KB Output is correct
2 Correct 40 ms 71500 KB Output is correct
3 Correct 42 ms 71684 KB Output is correct
4 Correct 38 ms 70824 KB Output is correct
5 Correct 40 ms 71116 KB Output is correct
6 Correct 44 ms 71428 KB Output is correct
7 Correct 37 ms 71048 KB Output is correct
8 Correct 51 ms 71284 KB Output is correct
9 Correct 47 ms 71712 KB Output is correct
10 Correct 54 ms 71712 KB Output is correct
11 Correct 41 ms 71780 KB Output is correct
12 Correct 45 ms 72588 KB Output is correct
13 Correct 48 ms 72628 KB Output is correct
14 Correct 51 ms 72328 KB Output is correct
15 Correct 46 ms 72932 KB Output is correct
16 Correct 45 ms 72244 KB Output is correct
17 Correct 44 ms 72660 KB Output is correct
18 Correct 48 ms 73284 KB Output is correct
19 Correct 49 ms 72252 KB Output is correct
20 Correct 45 ms 72620 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70744 KB Output is correct
2 Correct 40 ms 71500 KB Output is correct
3 Correct 42 ms 71684 KB Output is correct
4 Correct 38 ms 70824 KB Output is correct
5 Correct 40 ms 71116 KB Output is correct
6 Correct 44 ms 71428 KB Output is correct
7 Correct 37 ms 71048 KB Output is correct
8 Correct 51 ms 71284 KB Output is correct
9 Correct 47 ms 71712 KB Output is correct
10 Correct 54 ms 71712 KB Output is correct
11 Correct 41 ms 71780 KB Output is correct
12 Correct 45 ms 72588 KB Output is correct
13 Correct 48 ms 72628 KB Output is correct
14 Correct 51 ms 72328 KB Output is correct
15 Correct 46 ms 72932 KB Output is correct
16 Correct 45 ms 72244 KB Output is correct
17 Correct 44 ms 72660 KB Output is correct
18 Correct 48 ms 73284 KB Output is correct
19 Correct 49 ms 72252 KB Output is correct
20 Correct 45 ms 72620 KB Output is correct
21 Correct 61 ms 75088 KB Output is correct
22 Correct 84 ms 77400 KB Output is correct
23 Correct 94 ms 79140 KB Output is correct
24 Correct 141 ms 83292 KB Output is correct
25 Correct 60 ms 76752 KB Output is correct
26 Correct 124 ms 83428 KB Output is correct
27 Correct 170 ms 82576 KB Output is correct
28 Correct 146 ms 86348 KB Output is correct
29 Correct 89 ms 79956 KB Output is correct
30 Correct 172 ms 84552 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 70744 KB Output is correct
2 Correct 40 ms 71500 KB Output is correct
3 Correct 42 ms 71684 KB Output is correct
4 Correct 38 ms 70824 KB Output is correct
5 Correct 40 ms 71116 KB Output is correct
6 Correct 44 ms 71428 KB Output is correct
7 Correct 37 ms 71048 KB Output is correct
8 Correct 51 ms 71284 KB Output is correct
9 Correct 47 ms 71712 KB Output is correct
10 Correct 54 ms 71712 KB Output is correct
11 Correct 849 ms 142356 KB Output is correct
12 Incorrect 2057 ms 205356 KB Output isn't correct
13 Halted 0 ms 0 KB -