Submission #535195

#	Time	Username	Problem	Language	Result	Execution time	Memory
535195		cig32	Parachute rings (IOI12_rings)	C++17	20 / 100	1780 ms	262148 KiB

rings

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 10;

int N;

int dsu[MAXN];
int cnt[MAXN]; // count of nodes w degree 1 in such component
int sz[MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}

void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}

void Init(int N_) {

  N = N_;
  for(int i=0; i<N; i++) dsu[i] = i, cnt[i] = 0, sz[i] = 1;

}

vector<int> adj[MAXN];

set<int> deg3, deg4;//deg4: at least 4, deg3: == 3
unordered_map<int, int> owo[MAXN];
int dailo = -1;
bool sad = 0;

set<int> well_fucked;
void Link(int A, int B) {
  
  adj[A].push_back(B);
  adj[B].push_back(A);
  owo[A][B] = owo[B][A] = 1;
  if(set_of(A) != set_of(B)) {
    int old1 = set_of(A);
    int old2 = set_of(B);
    union_(A, B);
    cnt[set_of(A)] = cnt[old1] + cnt[old2] - (adj[A].size() == 2) - (adj[B].size() == 2) + (adj[A].size() == 1) + (adj[B].size() == 1);
    sz[set_of(A)] = sz[old1] + sz[old2];
    if(well_fucked.size()) {
      auto it1 = well_fucked.lower_bound(old1);
      if(*it1 == old1) {
        well_fucked.erase(old1);
      }
      auto it2 = well_fucked.lower_bound(old2);
      if(*it2 == old2) {
        well_fucked.erase(old2);
      }
    }
  }
  else {
    cnt[set_of(A)] = cnt[set_of(A)] - (adj[A].size() == 2) - (adj[B].size() == 2) + (adj[A].size() == 1) + (adj[B].size() == 1);
  }
  if(cnt[set_of(A)] == 0) {
    well_fucked.insert(set_of(A));
  }
  if(cnt[set_of(A)] > 0 && *well_fucked.lower_bound(set_of(A)) == set_of(A)) {
    well_fucked.erase(set_of(A));
  }
  if(adj[A].size() == 3) {
    deg3.insert(A);
    if(dailo != -1) {
      if(!owo[dailo][A]) {
        sad = 1;
      }
    }
  }
  if(adj[B].size() == 3) {
    deg3.insert(B);
    if(dailo != -1) {
      if(!owo[dailo][B]) {
        sad = 1;
      }
    }
  }
  if(adj[A].size() == 4) {
    deg4.insert(A);
    deg3.erase(A);
    if(dailo == -1) {
      dailo = A;
      for(int x: deg3) {
        if(!owo[A][x]) {
          sad = 1; break;
        }
      }
    }
  }
  if(adj[B].size() == 4) {
    deg4.insert(B);
    deg3.erase(B);
    if(dailo == -1) {
      dailo = B;
      for(int x: deg3) {
        if(!owo[B][x]) {
          sad = 1; break;
        }
      }
    }
  }
}

int CountCritical() {
  if(deg4.size() > 1) return 0;
  if(deg4.size() == 1 && sad) return 0;
  else if(deg4.size() == 1 && well_fucked.empty()) return 1;
  else if(deg4.size() == 1) return 0;
  // deg4.size = 0
  if(deg3.size() > 4) return 0;
  if(deg3.size() <= 4 && deg3.size() >= 1) {
    set<int> ans;
    for(int x: deg3) {
      bool rip = 0;
      for(int y: deg3) {
        if(x != y && !owo[x][y]) rip = 1;
      }
      if(!rip) {
        ans.insert(x);
      }
    }
    for(int x: deg3) {
      for(int i=0; i<adj[x].size(); i++) {
        int uwu = 0;
        for(int j=0; j<adj[adj[x][i]].size(); j++) {
          uwu += (adj[adj[adj[x][i]][j]].size() == 3);
        }
        if(uwu == deg3.size()) ans.insert(adj[x][i]);
      }
    }
    // everything must be connected, else no solution
    vector<int> fin;
    for(int x: ans) {
      int d = cnt[set_of(x)];
      if(adj[x].size() == 1) d--;
      for(int y: adj[x]) if(adj[y].size() == 1) d--;
      for(int y: adj[x]) if(adj[y].size() == 2) d++;
      if(d > 0) fin.push_back(x);
    }
    return fin.size();
  }
  // deg3.size = deg4.size = 0
  // all nodes shld be (in theory) ok
  if(well_fucked.size() == 1) {
    return sz[set_of(*well_fucked.begin())];
  }
  if(well_fucked.size() > 1) {
    return 0;
  }
  return N;
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:126:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |       for(int i=0; i<adj[x].size(); i++) {
      |                    ~^~~~~~~~~~~~~~
rings.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for(int j=0; j<adj[adj[x][i]].size(); j++) {
      |                      ~^~~~~~~~~~~~~~~~~~~~~~
rings.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if(uwu == deg3.size()) ans.insert(adj[x][i]);
      |            ~~~~^~~~~~~~~~~~~~

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