제출 #73170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73170		funcsr	장난감 기차 (IOI17_train)	C++17	11 / 100	394 ms	5744 KiB

train

#include "train.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

int N, M;
vector<int> G[5000], R[5000];

vector<int> who_wins(vector<int> owner, vector<int> color, vector<int> U, vector<int> V) {
  N = owner.size(), M = U.size();
  vector<int> used(N);
  rep(i, M) G[U[i]].pb(V[i]), R[V[i]].pb(U[i]);
  bool allA = true, allB = true;
  for (int x : owner) if (x == 0) allA = false; else allB = false;
  queue<int> win;
  if (allA) {
    rep(s, N) {
      if (color[s] != 1) continue;
      rep(x, N) used[x] = false;
      queue<int> q;
      q.push(s);
      while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int t : G[x]) if (!used[t]) {
          used[t] = true;
          q.push(t);
        }
      }
      if (used[s]) win.push(s);
    }
  }
  else if (allB) {
    rep(s, N) {
      if (color[s] != 0) continue;
      rep(x, N) used[x] = false;
      queue<int> q;
      q.push(s);
      while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int t : G[x]) if (color[t] == 0 && !used[t]) {
          used[t] = true;
          q.push(t);
        }
      }
      if (used[s]) win.push(s);
    }
  }
  else abort();
  rep(i, N) used[i] = false;

  while (!win.empty()) {
    int x = win.front(); win.pop();
    if (used[x]) continue;
    used[x] = true;
    for (int t : R[x]) win.push(t);
  }
  return used;
}

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