oj.uz

Submission #577363

# Submission time Handle Problem Language Result Execution time Memory
577363 2022-06-14T15:33:30 Z Kanon Toy Train (IOI17_train) C++14
22 / 100
 1241 ms 99956 KB 
#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;
        }
      }
    }
  }

  while (true) {
    vector<bool> st(n);
    vector<int> deg(n);
    function<void(int, int)> dfs = [&](int v, int player) {
      for (int i : Rev[v]) {
        if (ret[i] != -1) {
          continue;
        }
        if (st[i]) {
          continue;
        }
        deg[i]--;
        if (owned[i] == player || (deg[i] == 0)) {
          st[i] = true;
          dfs(i, player);
        }
      }
    };

    auto spanning = [&](vector<bool> base, int reachable) {
      for (int i = 0; i < n; i++) {
        deg[i] = 0;
        if (ret[i] != -1) {
          continue;
        }
        for (int j : g[i]) {
          if (ret[j] == -1) {
            deg[i]++;
          }
        }
      }
      st = base;
      for (int i = 0; i < n; i++) {
        if (base[i]) {
          dfs(i, reachable);
        }
      }
    };

    vector<bool> removed(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && z[i]) {
        removed[i] = true;
      }
    }
    spanning(removed, 1);
    removed = st;

    vector<bool> lost = removed;
    bool change = false;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1) {
        lost[i] = !lost[i];
        if (lost[i]) {
          change = true;
        }
      }
    }
    if (!change) {
      break;
    }
    spanning(lost, 0);
    lost = st;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && lost[i]) {
        ret[i] = 0;
      }
    }
  }

  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 39 ms 49856 KB 3rd lines differ - on the 26th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Incorrect 1 ms 300 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 99956 KB Output is correct
2 Correct 504 ms 99904 KB Output is correct
3 Correct 588 ms 99852 KB Output is correct
4 Correct 1156 ms 99876 KB Output is correct
5 Correct 916 ms 99936 KB Output is correct
6 Correct 649 ms 99844 KB Output is correct
7 Correct 545 ms 99660 KB Output is correct
8 Correct 368 ms 99648 KB Output is correct
9 Correct 357 ms 99704 KB Output is correct
10 Correct 436 ms 99748 KB Output is correct
11 Correct 392 ms 99612 KB Output is correct
12 Correct 72 ms 99484 KB Output is correct
13 Correct 1192 ms 99908 KB Output is correct
14 Correct 1241 ms 99832 KB Output is correct
15 Correct 1166 ms 99888 KB Output is correct
16 Correct 1155 ms 99896 KB Output is correct
17 Correct 1134 ms 99836 KB Output is correct
18 Correct 767 ms 99524 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7380 KB Output is correct
2 Correct 164 ms 99324 KB Output is correct
3 Correct 221 ms 96648 KB Output is correct
4 Correct 60 ms 50620 KB Output is correct
5 Correct 391 ms 97648 KB Output is correct
6 Correct 334 ms 95948 KB Output is correct
7 Correct 318 ms 92356 KB Output is correct
8 Correct 165 ms 81124 KB Output is correct
9 Correct 10 ms 6496 KB Output is correct
10 Correct 19 ms 23764 KB Output is correct
11 Correct 12 ms 10476 KB Output is correct
12 Correct 19 ms 25664 KB Output is correct
13 Correct 636 ms 99764 KB Output is correct
14 Correct 378 ms 99564 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 80380 KB Output is correct
2 Incorrect 891 ms 78992 KB 3rd lines differ - on the 4th token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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