Submission #1093148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093148		juicy	Stranded Far From Home (BOI22_island)	C++17	100 / 100	91 ms	14008 KiB

island

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, m;
int a[N], pr[N];
long long s[N];
bool lose[N];

int find(int u) {
  if (u == pr[u]) {
    return u;
  }
  int p = find(pr[u]);
  lose[u] |= lose[pr[u]];
  return pr[u] = p;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pr[i] = i, s[i] = a[i];
  }
  vector<array<int, 3>> e;
  while (m--) {
    int x, y; cin >> x >> y;
    if (a[x] > a[y]) {
      swap(x, y);
    }
    e.push_back({a[y], x, y});
  }
  sort(e.begin(), e.end());
  for (auto [w, u, v] : e) {
    u = find(u), v = find(v);
    if (u ^ v) {
      lose[u] = s[u] < a[v];
      pr[u] = v;
      s[v] += s[u];
    }
  }
  for (int i = 1; i <= n; ++i) {
    find(i);
    cout << (lose[i] ? 0 : 1);
  }
  return 0;
}

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