Submission #1208723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208723		LIA	Parachute rings (IOI12_rings)	C++17	0 / 100	4094 ms	28992 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;
bool dfs(ll ch, ll node, ll par) {
  vis[node] = 1;
  for (auto it : g[node]) {
   if (it == ch) continue;
    if (it!= par && vis[it]) return false;
    if (it!= par && !vis[it]) {
      if (!dfs(ch,it, node)) return false;
    }
  }
  return true;
}

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

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) {
    bool b = 1;
    vis.assign(n,false);
    loop(j,0,n) {
      if (j!=i && !vis[j]) {
        if (!dfs(i,j,-1)) b= false;
      }
    }
    if (b) ans++;
  }
  return ans;
}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

void Init(int N);
int CountCritical();
void Link(int a, int b);

int main() {
  int tmp;

  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);

  int N, L;
  tmp = scanf("%d %d", &N, &L);
  assert(tmp == 2);
  Init(N);

  int i;
  for (i = 0; i < L; i++) {
    int A, B;
    tmp = scanf("%d", &A);
    if (A == -1) {
      int critical;
      critical = CountCritical();
      printf("%d\n", critical);
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;

}

*/

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