oj.uz

Submission #576800

# Submission time Handle Problem Language Result Execution time Memory
576800 2022-06-13T14:27:46 Z Kanon Toy Train (IOI17_train) C++14
11 / 100
 608 ms 99256 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);
  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 = 0; player < 1; 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 15 ms 26068 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 5 ms 1108 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 7 ms 6996 KB Output is correct
2 Correct 156 ms 98888 KB Output is correct
3 Correct 237 ms 96332 KB Output is correct
4 Correct 58 ms 50248 KB Output is correct
5 Correct 381 ms 97044 KB Output is correct
6 Correct 320 ms 95504 KB Output is correct
7 Correct 301 ms 91820 KB Output is correct
8 Correct 160 ms 80780 KB Output is correct
9 Correct 9 ms 6100 KB Output is correct
10 Correct 16 ms 23400 KB Output is correct
11 Correct 11 ms 10112 KB Output is correct
12 Correct 18 ms 25172 KB Output is correct
13 Correct 608 ms 99240 KB Output is correct
14 Correct 381 ms 99256 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 522 ms 79896 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 15 ms 26068 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -