Submission #576798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
576798	2022-06-13T14:26:30 Z	Kanon	Toy Train (IOI17_train)	C++14	11 / 100	1259 ms	99688 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);
  for (int i = 0; i < m; i++) {
    g[From[i]].push_back(To[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 = 1; 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;

  vector<bool> Ze(n);
  while (true) {
    bool change = false;
    for (int i = 0; i < n; i++) {
      if (ret[i] != -1) {
        continue;
      }
      if (Ze[i]) {
        continue;
      }
      bool ok = false;
      if (owned[i] == 1) {
        for (int j : g[i]) {
          if (ret[j] != -1) {
            continue;
          }
          if (Ze[j] || z[j]) {
            ok = true;
          }
        }
      } else {
        bool rev = false;
        for (int j : g[i]) {
          if (ret[j] != -1) {
            continue;
          }
          if (Ze[j] || z[j]) {
            continue;
          }
          rev = true;
        }
        ok = !rev;
      }
      if (ok) {
        Ze[i] = true;
        change = true;
      }
    }
    if (!change) {
      break;
    }
  }

  for (int i = 0; i < n; i++) {
    if (ret[i] == -1) {
      if (Ze[i]) {
        ret[i] = 1;
      } else {
        ret[i] = 0;
      }
    }
  }
  return ret;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	24 ms	49364 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	1 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	259 ms	99376 KB	Output is correct
2	Correct	236 ms	99560 KB	Output is correct
3	Correct	231 ms	99688 KB	Output is correct
4	Correct	1174 ms	99524 KB	Output is correct
5	Correct	1002 ms	99444 KB	Output is correct
6	Correct	655 ms	99292 KB	Output is correct
7	Correct	568 ms	99292 KB	Output is correct
8	Correct	384 ms	99336 KB	Output is correct
9	Correct	353 ms	99280 KB	Output is correct
10	Correct	472 ms	99264 KB	Output is correct
11	Correct	407 ms	99244 KB	Output is correct
12	Correct	85 ms	99212 KB	Output is correct
13	Correct	1259 ms	99468 KB	Output is correct
14	Correct	1227 ms	99520 KB	Output is correct
15	Correct	1191 ms	99532 KB	Output is correct
16	Correct	1189 ms	99444 KB	Output is correct
17	Correct	1248 ms	99464 KB	Output is correct
18	Correct	402 ms	99392 KB	Output is correct