제출 #1093147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1093147		juicy	Stranded Far From Home (BOI22_island)	C++17	10 / 100	309 ms	524288 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, 2>> e;
  while (m--) {
    int x, y; cin >> x >> y;
    if (a[x] > a[y]) {
      swap(x, y);
    }
    e.push_back({x, y});
  }
  sort(e.begin(), e.end(), [&](const auto &i, const auto &j) {
    return a[i[1]] < a[j[1]];
  });
  for (auto [u, v] : e) {
    u = find(u);
    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: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35