oj.uz

Submission #576792

# Submission time Handle Problem Language Result Execution time Memory
576792 2022-06-13T14:00:40 Z Kanon Toy Train (IOI17_train) C++14
23 / 100
 856 ms 99608 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 < 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;
        }
      }

    }

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

  }

  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 36 ms 49468 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 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 99608 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 8 ms 7124 KB Output is correct
2 Correct 163 ms 99272 KB Output is correct
3 Correct 221 ms 96496 KB Output is correct
4 Correct 58 ms 50428 KB Output is correct
5 Correct 402 ms 97268 KB Output is correct
6 Correct 356 ms 95816 KB Output is correct
7 Correct 317 ms 92048 KB Output is correct
8 Correct 153 ms 80848 KB Output is correct
9 Correct 9 ms 6292 KB Output is correct
10 Correct 17 ms 23524 KB Output is correct
11 Correct 11 ms 10172 KB Output is correct
12 Correct 17 ms 25400 KB Output is correct
13 Correct 601 ms 99456 KB Output is correct
14 Correct 365 ms 99376 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 80120 KB Output is correct
2 Correct 856 ms 78840 KB Output is correct
3 Correct 305 ms 60112 KB Output is correct
4 Correct 277 ms 50344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 49 ms 50432 KB Output is correct
7 Correct 28 ms 1400 KB Output is correct
8 Correct 30 ms 1332 KB Output is correct
9 Correct 27 ms 1364 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 33 ms 2000 KB Output is correct

Subtask #6
0 / 51.0

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