Submission #577089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577089	2022-06-14T04:17:58 Z	Kanon	Toy Train (IOI17_train)	C++14	11 / 100	1288 ms	99988 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;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	38 ms	49720 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	263 ms	99724 KB	Output is correct
2	Correct	271 ms	99888 KB	Output is correct
3	Correct	243 ms	99872 KB	Output is correct
4	Correct	1187 ms	99836 KB	Output is correct
5	Correct	929 ms	99808 KB	Output is correct
6	Correct	654 ms	99660 KB	Output is correct
7	Correct	554 ms	99688 KB	Output is correct
8	Correct	359 ms	99788 KB	Output is correct
9	Correct	364 ms	99640 KB	Output is correct
10	Correct	431 ms	99676 KB	Output is correct
11	Correct	384 ms	99532 KB	Output is correct
12	Correct	69 ms	99500 KB	Output is correct
13	Correct	1237 ms	99988 KB	Output is correct
14	Correct	1288 ms	99968 KB	Output is correct
15	Correct	1235 ms	99900 KB	Output is correct
16	Correct	1210 ms	99900 KB	Output is correct
17	Correct	1202 ms	99924 KB	Output is correct
18	Correct	410 ms	99516 KB	Output is correct