Submission #1319220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319220		tsetsenbileg	Parachute rings (IOI12_rings)	C++20	0 / 100	297 ms	44144 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
int n;
vector<vector<int>> edge;
vector<int> three, more;
set<int> only;
bool no = 0;
bitset<1000000> crit;

void insert(int A) {
  if (edge[A].size() == 3) {
    if (!only.empty()) {
      only.insert(A);
      for (auto i : edge[A]) {
        only.insert(i);
      }
    }
    else {
      set<int> nonly;
      if (only.count(A)) nonly.insert(A);
      for (auto i : edge[A]) {
        if (only.count(i)) {
          nonly.insert(i);
        }
      }
      if (nonly.empty()) {
        no = 1;
      }
      only = nonly;
    }
  }
  if (edge[A].size() > 3) {
    set<int> nonly;
    if (only.count(A)) {
      nonly.insert(A);
    }
    else {
      no = 1;
    }
    only = nonly;
  }
}

void Init(int N_) {
  n = N_;
  edge.resize(n);
}

void Link(int A, int B) {
  edge[A].pb(B);
  edge[B].pb(A);
  if (no) return;
  insert(A);
  insert(B);
}

int CountCritical() {
  if (no) return 0;
  if (only.empty()) return n;
  return only.size();
}

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