Submission #577096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577096	2022-06-14T04:27:14 Z	Kanon	Toy Train (IOI17_train)	C++14	11 / 100	1233 ms	99892 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	40 ms	49652 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	267 ms	99812 KB	Output is correct
2	Correct	252 ms	99660 KB	Output is correct
3	Correct	248 ms	99648 KB	Output is correct
4	Correct	1187 ms	99552 KB	Output is correct
5	Correct	947 ms	99576 KB	Output is correct
6	Correct	673 ms	99504 KB	Output is correct
7	Correct	601 ms	99568 KB	Output is correct
8	Correct	386 ms	99464 KB	Output is correct
9	Correct	389 ms	99404 KB	Output is correct
10	Correct	441 ms	99380 KB	Output is correct
11	Correct	411 ms	99412 KB	Output is correct
12	Correct	73 ms	99296 KB	Output is correct
13	Correct	1223 ms	99892 KB	Output is correct
14	Correct	1212 ms	99660 KB	Output is correct
15	Correct	1233 ms	99600 KB	Output is correct
16	Correct	1211 ms	99620 KB	Output is correct
17	Correct	1206 ms	99604 KB	Output is correct
18	Correct	423 ms	99660 KB	Output is correct