Submission #577095

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577095	2022-06-14T04:25:54 Z	Kanon	Toy Train (IOI17_train)	C++14	11 / 100	1272 ms	99820 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]) {
          assert(ret[i] != (player ^ 1));
          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;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	36 ms	49688 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	3rd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	264 ms	99764 KB	Output is correct
2	Correct	236 ms	99660 KB	Output is correct
3	Correct	243 ms	99644 KB	Output is correct
4	Correct	1186 ms	99580 KB	Output is correct
5	Correct	921 ms	99536 KB	Output is correct
6	Correct	655 ms	99528 KB	Output is correct
7	Correct	535 ms	99540 KB	Output is correct
8	Correct	391 ms	99404 KB	Output is correct
9	Correct	367 ms	99468 KB	Output is correct
10	Correct	457 ms	99404 KB	Output is correct
11	Correct	418 ms	99504 KB	Output is correct
12	Correct	87 ms	99336 KB	Output is correct
13	Correct	1272 ms	99720 KB	Output is correct
14	Correct	1258 ms	99752 KB	Output is correct
15	Correct	1211 ms	99668 KB	Output is correct
16	Correct	1211 ms	99820 KB	Output is correct
17	Correct	1241 ms	99604 KB	Output is correct
18	Correct	410 ms	99432 KB	Output is correct