oj.uz

Submission #577359

# Submission time Handle Problem Language Result Execution time Memory
577359 2022-06-14T15:24:39 Z Kanon Toy Train (IOI17_train) C++14
11 / 100
 960 ms 99984 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;
    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 38 ms 49800 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 300 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 262 ms 99984 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 10 ms 7380 KB Output is correct
2 Correct 179 ms 99524 KB Output is correct
3 Correct 224 ms 96672 KB Output is correct
4 Correct 61 ms 50776 KB Output is correct
5 Correct 406 ms 97540 KB Output is correct
6 Correct 354 ms 95948 KB Output is correct
7 Correct 342 ms 92352 KB Output is correct
8 Correct 164 ms 81280 KB Output is correct
9 Correct 10 ms 6484 KB Output is correct
10 Correct 19 ms 23860 KB Output is correct
11 Correct 13 ms 10464 KB Output is correct
12 Correct 20 ms 25684 KB Output is correct
13 Correct 645 ms 99768 KB Output is correct
14 Correct 391 ms 99756 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 80432 KB Output is correct
2 Incorrect 960 ms 79060 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 38 ms 49800 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -