Submission #577519

#	Time	Username	Problem	Language	Result	Execution time	Memory
577519		Kanon	Toy Train (IOI17_train)	C++14	100 / 100	1186 ms	100084 KiB

train

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);


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);
  vector<vector<int>> Rev(n);
  for (int i = 0; i < m; i++) {
    g[From[i]].push_back(To[i]);
    Rev[To[i]].push_back(From[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]) {
          assert(ret[i] != (player ^ 1));
          ret[i] = player;
        }
      }
    }
  }

  vector<bool> st(n);
  vector<int> deg(n);
  bool added;
  function<void(int, int)> dfs = [&](int v, int player) {
    for (int i : Rev[v]) {
      if (ret[i] != -1) {
        continue;
      }
      if (st[i]) {
        continue;
      }
      deg[i]--;
      if (owned[i] == player || (deg[i] == 0)) {
        st[i] = true;
        added = true;
        dfs(i, player);
      }
    }
  };

  auto spanning = [&](vector<bool> &base, int reachable, bool hard = false) {
    added = false;
    for (int i = 0; i < n; i++) {
      deg[i] = 0;
      if (ret[i] != -1) {
        continue;
      }
      for (int j : g[i]) {
        if (ret[j] == -1 || hard) {
          deg[i]++;
        }
      }
    }
    st = base;
    for (int i = 0; i < n; i++) {
      if (base[i]) {
        dfs(i, reachable);
      }
    }
    base = st;
    return added;
  };

  while (true) {
    vector<bool> bwin(n);
    vector<bool> awin(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] == 0) {
        bwin[i] = true;
      }
      if (ret[i] == 1) {
        awin[i] = true;
      }
    }

    bool change = spanning(awin, 1, true) | spanning(bwin, 0, true);
    if (!change) {
      break;
    }
    for (int i = 0; i < n; i++) {
      if (bwin[i]) {
        ret[i] = 0;
      }
      if (awin[i]) {
        ret[i] = 1;
      }
      assert(!awin[i] || !bwin[i]);
    }
  }

  while (true) {
    vector<bool> removed(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && z[i]) {
        removed[i] = true;
      }
    }
    spanning(removed, 1);
    removed = st;

    vector<bool> lost = removed;
    bool change = false;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1) {
        lost[i] = !lost[i];
        if (lost[i]) {
          change = true;
        }
      }
    }
    if (!change) {
      break;
    }
    spanning(lost, 0);
    lost = st;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && lost[i]) {
        ret[i] = 0;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    if (ret[i] == -1) {
      ret[i] = 1;
    }
  }

  return ret;

}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51