oj.uz

Submission #576796

# Submission time Handle Problem Language Result Execution time Memory
576796 2022-06-13T14:18:22 Z Kanon Toy Train (IOI17_train) C++14
11 / 100
 934 ms 99424 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 37 ms 49412 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 331 ms 99424 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 174 ms 99000 KB Output is correct
3 Correct 219 ms 96204 KB Output is correct
4 Correct 70 ms 50244 KB Output is correct
5 Correct 406 ms 97044 KB Output is correct
6 Correct 355 ms 95416 KB Output is correct
7 Correct 327 ms 91744 KB Output is correct
8 Correct 179 ms 80748 KB Output is correct
9 Correct 8 ms 6100 KB Output is correct
10 Correct 17 ms 23296 KB Output is correct
11 Correct 10 ms 9940 KB Output is correct
12 Correct 20 ms 25172 KB Output is correct
13 Correct 688 ms 99180 KB Output is correct
14 Correct 387 ms 99076 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 79924 KB Output is correct
2 Correct 934 ms 78680 KB Output is correct
3 Correct 330 ms 59836 KB Output is correct
4 Correct 295 ms 50160 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 50 ms 50304 KB Output is correct
7 Correct 30 ms 1276 KB Output is correct
8 Incorrect 35 ms 1288 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 37 ms 49412 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -