oj.uz

Submission #577361

# Submission time Handle Problem Language Result Execution time Memory
577361 2022-06-14T15:27:19 Z Kanon Toy Train (IOI17_train) C++14
11 / 100
 686 ms 99752 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 (false) {
    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;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1) {
        lost[i] = !lost[i];
      }
    }
    spanning(lost, 0);
    if (count(lost.begin(), lost.end(), 1) == 0) {
      break;
    }
    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 36 ms 49672 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
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 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7252 KB Output is correct
2 Correct 171 ms 99292 KB Output is correct
3 Correct 242 ms 96512 KB Output is correct
4 Correct 59 ms 50536 KB Output is correct
5 Correct 417 ms 97532 KB Output is correct
6 Correct 336 ms 95756 KB Output is correct
7 Correct 327 ms 92068 KB Output is correct
8 Correct 192 ms 81028 KB Output is correct
9 Correct 11 ms 6316 KB Output is correct
10 Correct 21 ms 23648 KB Output is correct
11 Correct 11 ms 10352 KB Output is correct
12 Correct 19 ms 25448 KB Output is correct
13 Correct 686 ms 99496 KB Output is correct
14 Correct 395 ms 99412 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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