oj.uz

Submission #576802

# Submission time Handle Problem Language Result Execution time Memory
576802 2022-06-13T14:30:30 Z Kanon Toy Train (IOI17_train) C++14
11 / 100
 894 ms 99500 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;
        }
      }

    }
  }

  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 40 ms 49464 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 352 ms 99500 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 6996 KB Output is correct
2 Correct 170 ms 98968 KB Output is correct
3 Correct 233 ms 96204 KB Output is correct
4 Correct 57 ms 50248 KB Output is correct
5 Correct 413 ms 96972 KB Output is correct
6 Correct 361 ms 95532 KB Output is correct
7 Correct 327 ms 91700 KB Output is correct
8 Correct 159 ms 80660 KB Output is correct
9 Correct 8 ms 6100 KB Output is correct
10 Correct 17 ms 23380 KB Output is correct
11 Correct 11 ms 9940 KB Output is correct
12 Correct 19 ms 25172 KB Output is correct
13 Correct 668 ms 99268 KB Output is correct
14 Correct 387 ms 99148 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 79996 KB Output is correct
2 Correct 894 ms 78684 KB Output is correct
3 Correct 303 ms 59852 KB Output is correct
4 Correct 305 ms 50232 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 45 ms 50248 KB Output is correct
7 Correct 25 ms 1292 KB Output is correct
8 Incorrect 28 ms 1236 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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