Submission #789988

#	Time	Username	Problem	Language	Result	Execution time	Memory
789988		peteza	Parachute rings (IOI12_rings)	C++14	Compilation error	0 ms	0 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; cool = 1;
        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]++;
                    int I = fpar(i), E = fpar(e);
                    if(i < e && I == E) cool = 0;
                    par[I] = 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);
    }
};

dat elig[4];

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_; cluster = inited = cans = 0;
  for(int i=0;i<=N;i++) adj[i].clear();
  for(int i=0;i<=N;i++) deg[i] = 0, 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;
        int celig = 0;
        for(auto E:adj[todo])
            elig[celig++] =dat(E);
        elig[celig++] = dat(todo);
        for(auto &e:elig) cans += e.cool;
    } else {
        cans = 0;
        for(auto i=0;i<4;i++) {
            auto &e = elig[i];
            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:50:11: error: no matching function for call to 'dat::dat()'
   50 | dat elig[4];
      |           ^
rings.cpp:22:5: note: candidate: 'dat::dat(int)'
   22 |     dat (int x) {
      |     ^~~
rings.cpp:22:5: note:   candidate expects 1 argument, 0 provided
rings.cpp:15:8: note: candidate: 'constexpr dat::dat(const dat&)'
   15 | struct dat {
      |        ^~~
rings.cpp:15:8: note:   candidate expects 1 argument, 0 provided
rings.cpp:15:8: note: candidate: 'constexpr dat::dat(dat&&)'
rings.cpp:15:8: note:   candidate expects 1 argument, 0 provided
rings.cpp: In function 'void Init(int)':
rings.cpp:64:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   64 |   N = N_; cluster = inited = cans = 0;
      |                              ~~~~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:113:9: warning: unused variable 'res' [-Wunused-variable]
  113 |     int res = mg(pA, pB);
      |         ^~~