Submission #1307257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307257		ayaz	Stranded Far From Home (BOI22_island)	C++20	10 / 100	1097 ms	16504 KiB

island

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define line() "author : AyazN";
#endif

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int sz = 300500, inf = 1000000000;
const ll mod = 1000000007, INF = 1000000000000000000;
vi g[sz];
int a[sz], n, m;
void precompute() {}
struct DSU {
  vector<int> p, sz;
  int n, compo;
  void init(int _n) {
    n = _n;
    compo = n;
    p.resize(n + 1);
    sz.resize(n + 1, 1);
    for (int i = 1; i <= n; i++) p[i] = i;
  }
  int getpar(int x) {
    if (p[x] != x) p[x] = getpar(p[x]);
    return p[x];
  }
  void connect(int x, int y) {
    int a = getpar(x);
    int b = getpar(y);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
  }
  bool same(int x, int y) {
    return getpar(x) == getpar(y);
  }
};
bool bfs(int s) {
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  vi used(n + 1);
  used[s] = 1;
  int tot = a[s];
  for (auto v : g[s]) 
    pq.push({a[v], v});
  while (!pq.empty() && pq.top().first <= tot) {
    auto [d, u] = pq.top();
    pq.pop();
    used[u] = 1;
    tot += a[u];
    for (auto &v : g[u]) {
      if (!used[v]) {
        pq.push({a[v], v});
      }
    }
  }
  return (accumulate(used.begin() + 1, used.end(), 0) == n);
}
signed main() {
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int u = 1; u <= n; u++) {
    sort(all(g[u]), [&](int i, int j) {
      return a[j] > a[i];
    });
  }
  for (int i = 1; i <= n; i++) {
    cout << bfs(i);
  }
}

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