Submission #789961

#	Time	Username	Problem	Language	Result	Execution time	Memory
789961		peteza	Parachute rings (IOI12_rings)	C++14	20 / 100	4059 ms	72120 KiB

rings

#include <bits/stdc++.h>
using namespace std;

int N;
int cluster = 0;

int h[1000005];
int par[1000005];
bool vis[1000005];
bool inited = 0;
int cans = 0;
int deg[1000005], cmx;
vector<int> adj[1000005];

struct dat {
    int ign = -1;
    int deg[1000005] = {}, par[1000005];
    bool cool = 1;
    int fpar(int x) {
        return x == par[x] ? x : par[x] = fpar(par[x]);
    }
    dat (int x) {
        ign = x;
        for(int i=0;i<N;i++) par[i] = i;
        for(int i=0;i<N;i++) {
            if(i == ign) continue;
            for(int e:adj[i]) {
                if(e != ign) {
                    deg[i]++;
                    par[fpar(i)] = fpar(e);
                };
            }
            if(deg[i] >= 3) {
                cool = 0;
                return ;
            }
        }
    }
    void upd(int a, int b) {
        if(a == ign || b == ign) return;
        deg[a]++; deg[b]++;
        if(deg[a] >= 3 || deg[b] >= 3) cool = 0;
        if(fpar(a) == fpar(b)) cool = 0;
        par[fpar(a)] = fpar(b);
    }
};

vector<dat> elig;

int mg(int x, int y) {
  if(h[x] < h[y]) return par[x] = y;
  if(h[x] == h[y]) h[x]++;
  return par[y] = x;
}

int fpar(int x) {
  return x == par[x] ? x : fpar(par[x]);
}

void Init(int N_) {
    cmx = 0;
  N = N_; inited = cans = 0;
  elig.clear();
  for(int i=0;i<=N;i++) adj[i].clear();
  for(int i=0;i<=N;i++) h[i] = 0, par[i] = i;
}

void dfs(int a) {
    if(vis[a]) return ;
    vis[a] = 1;
    cans++;
    for(int e:adj[a]) dfs(e);
}

void Link(int A, int B) {
  if(cluster >= 2) return;
  adj[A].push_back(B); adj[B].push_back(A);
  ++deg[A]; ++deg[B];
  cmx = max(cmx, deg[A]);
  cmx = max(cmx, deg[B]);
  if(cmx >= 3) {
    //initialize
    if(!inited) {
        cans = 0;
        inited = 1;
        int todo = A;
        if(deg[B] == 3) todo = B;
        for(auto E:adj[todo])
            elig.emplace_back(dat(E));
        elig.emplace_back(dat(todo));
        for(auto &e:elig) cans += e.cool;
    } else {
        cans = 0;
        for(auto it = elig.begin(); it != elig.end(); it++) {
            auto &e = *it;
            if(!e.cool) continue;
            e.upd(A, B);
            if(!e.cool) continue;
            cans++;
        }
    }
    return;
  }

  int pA = fpar(A), pB = fpar(B);
  if(pA == pB) {
    cluster++;
    memset(vis, 0, sizeof vis);
    dfs(A);
  } else {
    int res = mg(pA, pB); 
  }
}

int CountCritical() {
  if(cluster >= 2) 
    return 0;
  if(inited) return cans;
  if(!cluster)
    return N;
  //cluster count is equal to 1
  return cans;
}

/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/

Compilation message (stderr)

rings.cpp: In function 'void Init(int)':
rings.cpp:62:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |   N = N_; inited = cans = 0;
      |                    ~~~~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:111:9: warning: unused variable 'res' [-Wunused-variable]
  111 |     int res = mg(pA, pB);
      |         ^~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31