Submission #73178

#	Time	Username	Problem	Language	Result	Execution time	Memory
73178		funcsr	Toy Train (IOI17_train)	C++17	16 / 100	20 ms	4364 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];
bool self[5000];
bool used[5000];
int ord[5000];
vector<int> W[5000];
void dfs(int x,vector<int> &ret) {
  if (used[x])return;
  used[x]=true;
  for (int t : G[x]) dfs(t, ret);
  ret.pb(x);
}
void dfs2(int x,int k){
  if (used[x])return;
  used[x]=true;
  ord[x]=k;
  for (int t : R[x]) dfs2(t, k);
}
vector<int> G2[5000];
bool earn[5000];
int memo[5000];

int dfs3(int x) {
  if (memo[x] != -1) return memo[x];
  int ret = earn[x];
  for (int t : G2[x]) ret |= dfs3(t);
  return memo[x] = ret;
}

vector<int> who_wins(vector<int> owner, vector<int> color, vector<int> U, vector<int> V) {
  N = owner.size(), M = U.size();
  bool case1 = true;
  rep(i, M) {
    G[U[i]].pb(V[i]);
    R[V[i]].pb(U[i]);
    if (!(V[i] == U[i] || V[i] == U[i]+1)) case1 = false;
  }
  bool allA = true, allB = true;
  for (int x : owner) if (x != 1) allA = false;
  for (int x : owner) if (x != 0) allB = false;

  //if (false){
  if (case1) {
    vector<int> win(N);
    for (int x=N-1; x>=0; x--) {
      bool loop = false;
      for (int t : G[x]) if (x == t) loop = true;
      bool next = false;
      for (int t : G[x]) if (x != t) next = true;

      //A
      if (owner[x] == 1) {
        if (color[x] && loop) win[x] = 1;
        else {
          if (next) win[x] = win[x+1];
          else win[x] = 0;
        }
      }
      else {
        if (!color[x] && loop) win[x] = 0;
        else {
          if (next) win[x] = win[x+1];
          else win[x] = 1;
        }
      }
    }
    return win;
  }
  else if (allA||allB) {
    rep(i, M) if (U[i]==V[i]) self[U[i]] = true;
    vector<int> vs;
    rep(i, N) used[i] = false;
    rep(i, N) if (!used[i]) dfs(i, vs);
    rep(i, N) used[i] = false;
    int K = 0;
    for (int i=vs.size()-1; i>=0; i--) if (!used[vs[i]]) dfs2(vs[i], K++);
    rep(i, N) W[ord[i]].pb(i);
    rep(i, N) if (!W[i].empty()) {
      if (W[i].size() == 1 && !self[W[i][0]]) continue;
      bool has = false;
      for (int x : W[i]) if (color[x]) has = true;

      if (allA) earn[i] |= has;
      else earn[i] |= !has;
    }
    rep(i, M) {
      if (ord[U[i]] != ord[V[i]]) {
        G2[ord[U[i]]].pb(ord[V[i]]);
      }
    }
    rep(i, K) memo[i] = -1;
    vector<int> ret(N, 0);
    if (allB) rep(i, N) ret[i] = 1;
    rep(i, K) if (dfs3(i)) {
      for (int x : W[i]) {
        if (allA) ret[x] = 1;
        else ret[x] = 0;
      }
    }
    return ret;
  }
  else abort();
}

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