oj.uz

Submission #810881

# Submission time Handle Problem Language Result Execution time Memory
810881 2023-08-06T17:07:41 Z erray Toy Train (IOI17_train) C++17
0 / 100
 2000 ms 1364 KB 
#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 end = Expand(ends, 0);
    bool change = false;
    for (int i = 0; i < N; ++i) {
      if (end[i]) {
        R[i] = false;
        change = true;
      }
    }
    if (!change) {
      for (int i = 0; i < N; ++i) {
        R[i] = !end[i];
      }
      break;
    }
  }
  return R;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 1364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 1108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 1236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -