Submission #1208809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208809		LIA	Parachute rings (IOI12_rings)	C++17	0 / 100	96 ms	6588 KiB

rings

#include <bits/stdc++.h>
using namespace std;
typedef int 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;
vll par, sz, ed;
ll find(ll v) {
  if (par[v] == v) return v;
  return par[v] = find(par[v]);
}

void uni(ll a, ll b) {
  ll x = find(a), y = find(b);
  if (x==y) {
    ed[x]++;
    return;
  }
  if (sz[x]<sz[y]) swap(x,y);
  sz[x]+=sz[y];
  ed[x]+=ed[y]+1;
  par[y] = x;
}
void Init(int N_) {
  n= N_;
  par.resize(n);
  sz.resize(n,1);
  ed.resize(n,0);
  loop(i,0,n) par[i] = i;
}

void Link(int a, int b) {
  uni(a,b);
}
int CountCritical() {
  ll ans = 0;
  vb vis(n);
  loop(i,0,n) {
    ll pari = find(i);
    if (!vis[pari]) {
      if (ed[pari] == sz[pari]-1) {
        vis[pari] = 1;
        ans++;
      }
    }
  }

  return ans;
}

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