제출 #394991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394991		usachevd0	장난감 기차 (IOI17_train)	C++14	100 / 100	646 ms	1348 KiB

train

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) {
  return y < x ? (x = y, true) : false; 
}
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

const int maxN = 5003;
using Set = bitset<maxN>;

vector<int> who_wins(vector<int> owner, vector<int> _Z, vector<int> e1, vector<int> e2) {
  int n = owner.size();
  int m = e1.size();
  vector<int> GR[n];
  vector<int> outdeg0(n);
  for (int j = 0; j < m; ++j) {
    GR[e2[j]].push_back(e1[j]);
  }
  for (int v = 0; v < n; ++v) {
    owner[v] ^= 1;
  }

  Set Z;
  for (int v = 0; v < n; ++v) {
    Z[v] = _Z[v];
  }
  Set enabled;
  for (int v = 0; v < n; ++v) {
    enabled[v] = true;
  }

  auto f = [&](int i, Set S) -> Set {
    vector<int> stk;
    vector<int> in_stk(n, false);

    auto add = [&](int v) {
      assert(enabled[v]);
      if (!in_stk[v]) {
        in_stk[v] = true;
        stk.push_back(v);
      }
    };
    for (int v = 0; v < n; ++v) {
      if (S[v] && enabled[v]) {
        add(v);
      }
    }

    vector<int> outdeg(n);
    for (int v = 0; v < n; ++v) {
      outdeg[v] = outdeg0[v];
    }
    Set ans;
    while (!stk.empty()) {
      int v = stk.back();
      stk.pop_back();
      ans[v] = 1;

      for (int u : GR[v]) if (enabled[u]) {
        if (owner[u] == i) {
          add(u);
        } else if (--outdeg[u] == 0) {
          add(u);
        }
      }
    }
    return ans;
  };

  while (true) {
    //cerr << "enabled: "; for (int v = 0; v < n; ++v) cerr << enabled[v]; cerr << endl;

    fill(all(outdeg0), 0);
    for (int v = 0; v < n; ++v) if (enabled[v]) {
      for (int u : GR[v]) if (enabled[u]) {
        ++outdeg0[u];
      }
    }
    Z &= enabled;
    if (!Z.count()) {
      return vector<int>(n, 0);
    }
    Set TZ = f(0, Z);
    Set B = TZ;
    for (int v = 0; v < n; ++v) if (enabled[v]) {
      B[v] = !B[v];
    }
    //cerr << "B: "; for (int v = 0; v < n; ++v) cerr << B[v]; cerr << endl;
    if (!B.count()) {
      vector<int> ans(n);
      for (int v = 0; v < n; ++v) {
        ans[v] = enabled[v];
      }
      return ans;
    }
    Set TB = f(1, B);
    //cerr << "TB: "; for (int v = 0; v < n; ++v) cerr << TB[v]; cerr << endl;
    enabled &= ~TB; 
  }
  throw;
}


#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m;
  cin >> n >> m;
  vector<int> a(n), r(n);
  for (auto& x : a) cin >> x;
  for (auto& x : r) cin >> x;
  vector<int> e1(m), e2(m);
  for (int j = 0; j < m; ++j) {
    cin >> e1[j] >> e2[j];
  }
  cout << who_wins(a, r, e1, e2) << '\n';

  return 0;
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51