Submission #1305532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305532		al95ireyiz	Stranded Far From Home (BOI22_island)	C++20	10 / 100	147 ms	620 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 2e3 + 5;

ll n, m, k = 0;

ll a[maxn];
vll g[maxn];
ll bfs(ll x){
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>q;
  vll vis(n + 1);
  vis[x] = 1;
  q.push({a[x], x});
  ll cm = 0, sz = 0, st = 1;
  while(!q.empty()){
    auto [tmpp, u] = q.top();
    if(cm < a[u] and !st) break;
    cm += a[u], sz ++, st = 0;
    q.pop();
    for(auto v : g[u]){
      if(vis[v]) continue;
      vis[v] = 1;
      q.push({a[v], v});
    }
  }
  // cerr << x << ' ' << sz << '\n';
  return sz;
}
void _() {
  cin >> n >> m;
  for(ll i = 1; i <= n; i ++){
    cin >> a[i];
  }
  for(ll i = 1, x, y; i <= m; i ++){
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for(ll i = 1; i <= n; i ++){
    sort(g[i].begin(), g[i].end(), [&](ll &x, ll &y){ return a[x] < a[y]; });
  }
  for(ll i = 1; i <= n; i ++){
    if(bfs(i) == n) cout << 1;
    else cout << 0;
  }
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}

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