Submission #640566

#	Time	Username	Problem	Language	Result	Execution time	Memory
640566		kith14	Stranded Far From Home (BOI22_island)	C++17	20 / 100	1083 ms	386592 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 = 2e5+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); 
  }
}

ll sub[N], pos[N];
void dfs(ll idx, ll par){
  sub[idx] = ar[idx];
  for (auto i : ed[idx]){
    if (i == par) continue;
    dfs(i,idx);
    sub[idx] += sub[i];
  }
}

void ser(ll idx, ll par){
  for (auto i : ed[idx]){
    if (i == par) continue;
    if (sub[i] >= ar[idx]){
      pos[i] = 1;
      ser(i,idx);
    }
  }
}

void sub2(){
  //root is at 1
  dfs(1,-1);
  pos[1] = 1;
  ser(1,-1);
  repp(i,1,n) cout << pos[i];
  cout << endl;
}

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

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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35