Submission #1290729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290729		turral	장난감 기차 (IOI17_train)	C++20	0 / 100	6 ms	1856 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);
    }
  }
 /* cout << u << ":\n";
  for (int v : G[u]){
    cout << v << ' ' << wins[v] << ", ";
  }
  cout << '\n' << res << '\n'; */

  wins[u] = res;
  return res;
}

void DFS_reverse(int u, bool bat, vector<vector<int> > & G, vector<int> & wins, vector<int> & a, vector<int> & inEdges){
  if (wins[u] != -1) return;

  if (a[u] == 1 || bat){
    wins[u] = 1;
  } else {
    inEdges[u]--;
    if (inEdges[u] == 0){
      wins[u] = 1;
    } else {
      return;
    }
  }

  for (int v : G[u]){
    DFS_reverse(v, false, G, wins, a, inEdges);
  }
}

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), F(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); // -1 idk, 0 no, 1 yea; // win = battery ()
  for (int i=0; i<N; ++i) {
    if (r[i] == 1) {
      DFS_reverse(i, true, F, wins, a, inEdgesF);
    } 
  }

  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';
}

4 9
1 0 1 0
0 1 0 0
0 1
0 0
0 2
2 1
1 2
2 3
3 1
3 0
1 3
---
1 1 1 0 
*/

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