Submission #810866

#	Time	Username	Problem	Language	Result	Execution time	Memory
810866		erray	Toy Train (IOI17_train)	C++17	11 / 100	7 ms	1364 KiB

train

#include "train.h"
//author: erray
#include <bits/stdc++.h>

using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/debug.h"
#else
  #define debug(...) (void) 37
#endif


std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> U, std::vector<int> V) { 
  int N = int(A.size());
  int M = int(U.size());
  vector<vector<int>> rg(N);
  vector<int> outdeg_def(N);
  for (int i = 0; i < M; ++i) {
    rg[V[i]].push_back(U[i]);
    outdeg_def[U[i]] += 1;
  }
  while (true) {
    debug(R);
    auto Expand = [&](vector<int> que, int side) {
      auto outdeg = outdeg_def;
      vector<bool> vis(N);
      for (auto v : que) {
        vis[v] = true;
      }
      for (int it = 0; it < int(que.size()); ++it) {
        int v = que[it];
        for (auto u : rg[v]) {
          if (!vis[u] && (A[u] == side || --outdeg[u] == 0)) {
            que.push_back(u);
            vis[u] = true;
          }
        }
      }
      return vis;
    };
    vector<int> stats;
    for (int i = 0; i < N; ++i) {
      if (R[i]) {
        stats.push_back(i);
      }
    }
    auto inv = Expand(stats, 1);
    vector<int> ends;
    for (int i = 0; i < N; ++i) {
      if (!inv[i]) {
        ends.push_back(i);
      }
    }
    auto new_R = Expand(ends, 0);
    bool change = false;
    for (int i = 0; i < N; ++i) {
      change |= R[i] == new_R[i];
      R[i] = !new_R[i];
    }
    if (!change) {
      break;
    }
  }
  return R;
}

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