Submission #1291115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291115		turral	Toy Train (IOI17_train)	C++20	0 / 100	2074 ms	99696 KiB

train

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

using namespace std;

int DFS_wins(int u, int p, vector<vector<int> > & G, vector<int> & visited, vector<int> & a, vector<int> & r, vector<int> battery){
  if (visited[u] == 1) return 1;
  if (visited[u] == -1) return battery[p] - battery[u] + r[u] > 0;
  visited[u] = -1;

  if (p != -1){
    battery[u] = battery[p] + r[u];
  } else {
    battery[u] = r[u];
  }

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

  visited[u] = 1;
  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);
  //vector<int> inEdgesF(N, 0);
  for (int i=0; i<M; ++i){
    G[u[i]].push_back(v[i]);
    //F[v[i]].push_back(u[i]);
    //inEdgesF[u[i]]++;
  }

  vector<int> wins(N, -1); 
  for (int i=0; i<N; ++i){
    vector<int> visited(N, 0), battery(N, 0);
    wins[i] = DFS_wins(i, -1, G, visited, a, r, battery);
  }  

  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