Submission #789946

#	Time	Username	Problem	Language	Result	Execution time	Memory
789946		peteza	Parachute rings (IOI12_rings)	C++14	20 / 100	4065 ms	76448 KiB

rings

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

int N;
int cluster = 0;

int role[1000005];
int h[1000005];
int par[1000005];
bool vis[1000005];
bool inited = 0;
int cans = 0;
vector<int> adj[1000005];
set<pair<int, int>> S;
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_) {
  N = N_; inited = 0;
  elig.clear();
  for(int i=0;i<=N;i++) adj[i].clear();
  for(int i=0;i<N;i++) S.emplace(0, i);
  for(int i=0;i<=N;i++) h[i] = 0, par[i] = i;
  memset(role, 0, sizeof role);
}

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;
  S.erase({adj[A].size(), A}); S.erase({adj[B].size(), B});
  adj[A].push_back(B); adj[B].push_back(A);
  S.emplace(adj[A].size(), A); S.emplace(adj[B].size(), B);
  //for(auto e:S) cout << e.first << ' ' << e.second << '\n';
  //cout << (--S.end())->first << '\n';
  if((--S.end())->first >= 3) {
    //initialize
    if(!inited) {
        inited = 1;
        auto e = *(--S.end());
        for(auto E:adj[e.second]) {
            dat neu(E);
            if(neu.cool)
                elig.emplace_back(neu);
        }
        dat neu(e.second);
        if(neu.cool)
            elig.emplace_back(neu);
    } else {
        for(auto it = elig.begin(); it != elig.end(); it++) {
            auto &e = *it;
            e.upd(A, B);
            if(e.cool) continue;
            elig.erase(it--);
        }
    }
    cans = elig.size();
    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 Link(int, int)':
rings.cpp:114:9: warning: unused variable 'res' [-Wunused-variable]
  114 |     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