Submission #1208800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208800		LIA	Parachute rings (IOI12_rings)	C++17	20 / 100	4090 ms	33092 KiB

rings

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
ll n;
vvll g;
vb vis;
ll in = 0;
ll cnt1 = 0, cnt2 = 0;
bool is = 1;
vll del;

void dfs(ll ch, ll node, ll par) {
  vis[node] = 1;
  in++;
  ll dar = 0;
  for (auto it : g[node]) {
    if (it==par && it!= ch) dar++;
    if (it==ch || it == par) continue;
    if (vis[it]) {
      is = false;
      continue;
    }
    dar++;
    dfs(ch, it, node);
  }
  if (dar!= 1 && dar!= 2) is = false;
  if (dar==1) cnt1++;
  if (dar==2) cnt2++;
}

void Init(int N_) {
  n= N_;
  g.resize(n);
  del.resize(n,1);
}

void Link(int a, int b) {
  g[a].push_back(b);
  g[b].push_back(a);
}
int CountCritical() {
  ll ans = 0;
  vis.resize(n, false);
  loop(i,0,n) {
    if (del[i]== -1) continue;
    bool b = 1;
    vis.assign(n,false);
    loop(j,0,n) {
      if (j!=i && !vis[j]) {
        in = 0;
        cnt1 = 0, cnt2 = 0;
        is = 1;
        dfs(i,j,-1);
        if (in==1) continue;
        if (!is || cnt1!=2 || cnt2!=(in-2)) {
          b = false;
        }
      }
    }
    if (b) ans++;
    else del[i] = -1;
  }
  return ans;
}

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