Submission #632407

#	Time	Username	Problem	Language	Result	Execution time	Memory
632407		lunchbox	Thousands Islands (IOI22_islands)	C++17	100 / 100	359 ms	33880 KiB

islands

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<vi, vi> pvv;
 
vi min_rot(vi v) {
  rotate(v.begin(), min_element(v.begin(), v.end()), v.end());
  return v;
}
 
variant<bool, vi> find_journey(int N, int M, vi u, vi v) {
  queue<int> s;
  vector<set<int>> in(N), out(N);
  for (int i = 0; i < M; i++) {
    out[u[i]].insert(i);
    in[v[i]].insert(i);
  }
  auto rf = [&](int x) {
    if (out[x].empty())
      s.push(x);
  };
  for (int i = 0; i < N; i++)
    rf(i);
  int q = 0;
  vi sf;
  while (1) {
    auto re = [&](int x) {
      for (auto it : in[x]) {
        out[u[it]].erase(it);
        rf(u[it]);
      }
      for (auto it : out[x])
        in[v[it]].erase(it);
    };
    for ( ; !s.empty(); s.pop()) {
      if (s.front() == q)
        return false;
      re(s.front());
    }
    if (out[q].size() == 1) {
      int edge = *out[q].begin();
      re(q);
      q = v[edge];
      sf.push_back(edge);
    } else {
      auto fnd = [&](int x, int e, bool b) {
        int y = v[e];
        vector<bool> z(N);
        vi p = {e};
        z[x] = b;
        for (; !z[y]; y = v[e]) {
          p.push_back(e = *out[y].begin());
          z[y] = true;
        }
        int last = -1;
        for (int i = 0; i < (int) p.size(); i++) {
          if (x == y)
            last = i;
          x = v[p[i]];
        }
        vi t, c;
        for (int i = 0; i < (int) p.size(); i++)
          if (i < last)
            t.push_back(p[i]);
          else
            c.push_back(p[i]);
        return pvv(t, c);
      };
      auto it = out[q].begin();
      pvv c1 = fnd(q, *it++, true), c2 = fnd(q, *it++, false);
      vi y;
      auto ad = [&](vi &v) {
        y.insert(y.end(), v.begin(), v.end());
        reverse(v.begin(), v.end());
      };
      ad(sf);
      bool eq = min_rot(c1.second) == min_rot(c2.second);
      for (int i = 0; i < 2; i++) {
        auto tr = [&](pvv &p1, pvv &p2) {
          ad(p1.first);
          ad(p1.second);
          if (eq)
            reverse(p2.second.begin(), p2.second.end());
          ad(p1.first);
        };
        tr(c1, c2);
        tr(c2, c1);
      }
      ad(sf);
      return y;
    }
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45