Submission #394985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
394985	2021-04-27T15:01:05 Z	usachevd0	Toy Train (IOI17_train)	C++17	0 / 100	16 ms	1308 KB

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 = 2003;
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]);
  }

  Set Z;
  for (int v : _Z) {
    Z[v] = 1;
  }
  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) {
      if (!in_stk[v]) {
        in_stk[v] = true;
        stk.push_back(v);
      }
    };
    for (int v = 0; v < n; ++v) {
      if (S[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 (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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	844 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1228 KB	Output is correct
2	Correct	8 ms	1308 KB	Output is correct
3	Correct	8 ms	1228 KB	Output is correct
4	Incorrect	8 ms	1208 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-