Submission #577092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577092	2022-06-14T04:23:09 Z	Kanon	Toy Train (IOI17_train)	C++14	Compilation error	0 ms	0 KB

train

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> who_wins(vector<int> owned, vector<int> z, vector<int> From, vector<int> To) {
  int n = owned.size();
  int m = To.size();
  vector<vector<int>> g(n);
  vector<vector<int>> Rev(n);
  for (int i = 0; i < m; i++) {
    g[From[i]].push_back(To[i]);
    Rev[To[i]].push_back(From[i]);
  }
 
  vector<int> ret(n, -1);
 
  {
    vector<int> was(n);
    vector<int> alive(n);
    function<void(int)> dfs = [&] (int v) {
      was[v] = 1;
      for (int i : g[v]) {
        if (alive[i] && !was[i]) {
          dfs(i);
        }
      }
    };
 
    auto winstate = [&](vector<int> keep, vector<int> nodes) {
      fill(alive.begin(), alive.end(), 0);
      for (int i : keep) {
        alive[i] = 1;
      }
 
      vector<vector<int>> r(n);
      for (int i = 0; i < n; i++) {
        if (!alive[i]) {
          continue;
        }
        dfs(i);
        r[i] = was;
        fill(was.begin(), was.end(), 0);
      }
 
      vector<bool> win(n);
      for (int i : nodes) {
        for (int j : g[i]) {
          if (alive[j] && r[j][i] == 1) {
            win[i] = true;
          }
        }
      }
      return win;
    };
 
    auto get_win = [&](vector<int> keep, vector<bool> &win) {
      while (true) {
        bool change = false;
        for (int i : keep) {
          if (win[i]) {
            continue;
          }
          for (int j : g[i]) {
            if (win[j]) {
              win[i] = true;
              change = true;
            }
          }
        }
        if (!change) {
          break;
        }
      }
    };
 
    for (int player = 0; player < 2; player++) {
      vector<int> keep;
      vector<int> nodes;
 
      for (int i = 0; i < n; i++) {
        if (owned[i] != player) {
          continue;
        }
        if (player == 1) {
          keep.push_back(i);
          if (z[i]) {
            nodes.push_back(i);
          }
        } else {
          if (!z[i]) {
            keep.push_back(i);
            nodes.push_back(i);
          }
        }
      }
 
      vector<bool> win = winstate(keep, nodes);
 
      if (player == 0) {
        keep.clear();
        for (int i = 0; i < n; i++) {
          if (owned[i] == player) {
            keep.push_back(i);
          }
        }
      }
 
      get_win(keep, win);
      for (int i = 0; i < n; i++) {
        if (win[i]) {
          ret[i] = player;
        } else {
          ret[i] = player ^ 1;
        }
      }
 
    }
  }
  return ret;
 
  while (true) {
    vector<bool> Ze(n);
    function<void(int)> dfs = [&](int v) {
      for (int i : Rev[v]) {
        if (ret[i] != -1) {
          continue;
        }
        if (Ze[i] || owned[i] == 0) {
          continue;
        }
        Ze[i] = true;
        dfs(i);
      }
    };
    for (int i = 0; i < n; i++) {
      if (!Ze[i] && z[i] && ret[i] == -1) {
        dfs(i);
      }
    }
 
    vector<bool> removed(n);
    vector<int> que;
    vector<int> deg(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] != -1) {
        continue;
      }
      for (int j : g[i]) {
        if (ret[j] == -1) {
          deg[i]++;
        }
      }
    }
 
    for (int i = 0; i < n; i++) {
      if (ret[i] != -1) {
        continue;
      }
      if (Ze[i] || z[i]) {
        removed[i] = true;
        que.push_back(i);
      }
    }
 
    for (int b = 0; b < (int) que.size(); b++) {
      int v = que[b];
      for (int i : Rev[v]) {
        if (ret[i] != -1) {
          continue;
        }
        deg[i]--;
        if (removed[i]) {
          continue;
        }
        if (owned[i] == 1 || deg[i] == 0) {
          que.push_back(i);
          removed[i] = 1;
        }
      }
    }
 
    function<void(int)> dfs1 = [&](int v) {
      for (int i : Rev[v]) {
        if (ret[i] == -1 && owned[i] == 0 && removed[i]) {
          ret[i] = 0;
          dfs1(i);
        }
      }
    };
 
    bool change = false;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && !removed[i]) {
        ret[i] = 0;
        change = true;
        dfs1(i);
      }
    }
 
    if (!change) {
      break;
    }
 
  }
 
  for (int i = 0; i < n; i++) {
    if (ret[i] == -1) {
      ret[i] = 1;
    }
  }
  return ret;
}

int main() {
  vector<int> win = who_wins({0, 1}, {1, 0}, {0, 0, 1, 1}, {0, 1, 0, 1});
  for (int i : win) {
    cerr << i << " ";
  }
  return 0;
}

Compilation message

/usr/bin/ld: /tmp/cczNmn16.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJtnP66.o:train.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status