Submission #1125537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125537		dynam1c	Stranded Far From Home (BOI22_island)	C++20	100 / 100	395 ms	23176 KiB

island

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
  int n;
  vector<int> up, sz;
  vector<ll> val;
  DSU(const vector<ll>& arr)
    : val(arr), n(arr.size()), up(arr.size()), sz(arr.size(), 1) {
    iota(up.begin(), up.end(), 0);
  }
  int find(int v) {
    return up[v] == v ? v : up[v] = find(up[v]);
  }
  bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return false;
    if (sz[u] < sz[v])
      swap(u, v); // sz[u] >= sz[v]
    sz[u] += sz[v];
    val[u] += val[v];
    up[v] = u;
    return true;
  }
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> arr(n);
  for (auto& e : arr)
    cin >> e;
  vector<vector<int>> graph(n);
  while (m--) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }

  vector<pair<int, int>> verts(n);
  priority_queue<pair<ll, int>> pq; // {-x, v}
  for (int i = 0; i < n; i++)
    verts[i] = {arr[i], i}, pq.emplace(-arr[i], i);
  sort(verts.begin(), verts.end());
  reverse(verts.begin(), verts.end());
  DSU dsu(arr);


  vector<ll> ans(n);
  ll tot = accumulate(arr.begin(), arr.end(), 0LL);
  while (!pq.empty()) {
    auto [x, v] = pq.top();
    pq.pop();
    x = -x;
    ans[v] = x;
    while (!verts.empty() && verts.back().first <= x) {
      int u = verts.back().second;
      for (int ne : graph[u])
        if (arr[ne] <= x)
          dsu.unite(u, ne);
      verts.pop_back();
    }
    ll nx = dsu.val[dsu.find(v)];
    if (x != nx)
      pq.emplace(-nx, v);
  }

  for (auto x : ans)
    cout << (x == tot);
  cout << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35