Submission #1290698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290698		turral	Toy Train (IOI17_train)	C++20	0 / 100	5 ms	1092 KiB

train

#include "train.h"
#include <iostream>
#include <vector>

using namespace std;

int DFS_wins(int u, vector<vector<int> > & G, vector<int> & wins, vector<int> & a){
  if (wins[u] != -1) return wins[u];
  wins[u] = 0;

  int res = a[u] ^ 1;
  for (int v : G[u]){
    if (a[u]){
      res |= DFS_wins(v, G, wins, a);
    } else {
      res &= DFS_wins(v, G, wins, a);
    }
  }

  wins[u] = res;
  return res;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
  int N = a.size(), M = u.size(); // 1 -> the battery person has it

  vector<vector<int> > G(N);
  for (int i=0; i<M; ++i){
    G[u[i]].push_back(v[i]);
  }

  vector<int> wins(N, -1); // -1 idk, 0 no, 1 yea; // win = battery ()
  for (int i=0; i<N; ++i) {
    if (r[i] == 1) wins[i] = 1;
  }

  for (int i=0; i<N; ++i){
    wins[i] = DFS_wins(i, G, wins, a);
  }

  return wins;
}

/*
int main(){
  int N, M; cin >> N >> M;

  vector<int> a(N), r(N), u(M), v(M);

  for (int & x : a) cin >> x;
  for (int & x : r) cin >> x;

  for (int i=0; i<M; ++i){
    cin >> u[i] >> v[i];
  }

  vector<int> w = who_wins(a,r,u,v);

  for (int n : w) cout << n << ' ';
  cout << '\n';
}
*/

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