Submission #535213

#	Time	Username	Problem	Language	Result	Execution time	Memory
535213		cig32	Parachute rings (IOI12_rings)	C++17	0 / 100	1394 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;
}

int CountCritical() {
  int ans = 0;
  for(int i=0; i<N; i++) {
    bool vis[N];
    for(int j=0; j<N; j++) vis[j] = 0;
    vis[i] = 1;
    bool ohno = 0;
    for(int j=0; j<N; j++) {
      if(!vis[j]) {
        queue<int> q;
        q.push(j);
        vector<int> v;
        while(q.size()) {
          int f = q.front(); q.pop();
          if(!vis[f]) {
            vis[f] = 1;
            v.push_back(adj[f].size() - owo[f][i]);
            for(int x: adj[f]) {
              if(!vis[x]) {
                q.push(x);
              }
            }
          }
        }
        if(v.size() > 1) {
          sort(v.begin(), v.end());
          if(v[0] != 1) ohno = 1;
          if(v[1] != 1) ohno = 1;
          for(int i=2; i<v.size(); i++) if(v[i] != 2) ohno = 1;
        }
        if(ohno) break;
      }
    }
    if(!ohno) {
      ans++;
    }
  }
  return ans;
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:68:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |           for(int i=2; i<v.size(); i++) if(v[i] != 2) ohno = 1;
      |                        ~^~~~~~~~~

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