제출 #640219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640219		andecaandeci	Stranded Far From Home (BOI22_island)	C++17	10 / 100	75 ms	644 KiB

island

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

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 2e3+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], vs[N];
ll x, y, k;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> v;
vector<ll> ed[N];

void input(){
  cin >> n >> m;
  repp(i,1,n) cin >> ar[i];
  repp(i,1,m){
    cin >> x >> y;
    ed[x].pb(y);
    ed[y].pb(x);
  }
}

void sub1(){
  repp(i,1,n){
    ll cur = ar[i], vst = 1;
    priority_queue<pairll, vector<pairll>, greater<pairll> > pq;
    queue<ll> q;
    q.push(i);
    vs[i] = i;
    while(q.size()){
      ll a = q.front();
      //cout << i << " " << a << endl;
      q.pop();
      for (auto nx : ed[a]){
        if (vs[nx] == i) continue;
        if (ar[nx] > cur){
          pq.push(mp(ar[nx],nx));
        }
        else{
          cur += ar[nx];
          vs[nx] = i;
          q.push(nx);
          vst++;
        }
      }
      while(pq.size() && pq.top().fr <= cur){
        pairll a = pq.top();
        pq.pop();
        cur += a.fr;
        vs[a.sc] = i;
        q.push(a.sc);
        vst++;
      }
    }
    cout << (vst == n); 
  }
}

void solve(){
  if (n <= 2e3 && m <= 2e3) sub1();
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

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