Submission #754262

#	Time	Username	Problem	Language	Result	Execution time	Memory
754262		lukameladze	Parachute rings (IOI12_rings)	C++17	100 / 100	2593 ms	254616 KiB

rings

# 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 (stderr)

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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31