답안 #810866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810866 2023-08-06T16:56:28 Z erray 장난감 기차 (IOI17_train) C++17
11 / 100
7 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 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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 852 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 0 ms 300 KB 3rd lines differ - on the 4th token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1340 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1080 KB Output is correct
2 Correct 5 ms 1204 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 6 ms 1340 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 5 ms 1236 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 5 ms 1204 KB Output is correct
10 Correct 5 ms 1236 KB Output is correct
11 Correct 5 ms 1364 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 5 ms 1212 KB Output is correct
14 Correct 5 ms 1236 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1236 KB Output is correct
2 Correct 5 ms 1236 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Incorrect 3 ms 852 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 852 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -