Submission #576798

#	Time	Username	Problem	Language	Result	Execution time	Memory
576798		Kanon	Toy Train (IOI17_train)	C++14	11 / 100	1259 ms	99688 KiB

train

#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 = 1; 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;
        } 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
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51