제출 #69492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69492		funcsr	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	1673 ms	106180 KiB

rings

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

int N;
vector<int> G[1000000];

void Init(int N_) {
  N = N_;
}

void Link(int a, int b) {
  //cout<<a<<"<->"<<b<<"\n";
  G[a].pb(b);
  G[b].pb(a);
}

int ord[1000000];
bool used[1000000];
int T[1000000], D[1000000];
bool bad[1000000];

void dfs(int x, int p, int r, int &all) {
  used[x] = true;
  ord[x] = r;
  for (int t : G[x]) if (t != p) {
    if (used[t]) {
      if (ord[x] > ord[t]) {
        // [ord[t], ord[x]]
        D[t]++, D[x]++;
        T[p]++, T[t]--;
        all++;
      }
      continue;
    }
    dfs(t, x, r+1, all);
  }
}
void dfs2(int x, int p) {
  used[x] = true;
  for (int t : G[x]) if (t != p && !used[t]) {
    dfs2(t, x);
    T[x] += T[t];
    if (T[t] >= 2) bad[x] = true;
  }
}

int CountCritical() {
  rep(i, N) used[i] = false, bad[i] = false, ord[i] = -1, T[i] = 0, D[i] = 0;
  int all = 0;
  rep(i, N) if (!used[i]) dfs(i, -1, 0, all);
  rep(i, N) used[i] = false;
  rep(i, N) if (!used[i]) dfs2(i, -1);

  int deg3 = 0;
  auto add = [&](int d) { if (d >= 3) deg3++; };
  auto rem = [&](int d) { if (d >= 3) deg3--; };
  rep(i, N) add(G[i].size());

  int ctr = 0;
  rep(x, N) {
    //if (T[x] >= 2 || T[x]+D[x] != all) continue;
    if (bad[x] || T[x]+D[x] != all) continue;

    rem(G[x].size());
    for (int t : G[x]) {
      rem(G[t].size());
      add(G[t].size()-1);
    }

    if (deg3 == 0) ctr++;

    for (int t : G[x]) {
      rem(G[t].size()-1);
      add(G[t].size());
    }
    add(G[x].size());
  }
  return ctr;
}

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