Submission #1099397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099397		epicci23	Stranded Far From Home (BOI22_island)	C++17	100 / 100	455 ms	80232 KiB

island

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5;
int s[N],par[N],val[N];
vector<int> v[N],comp[N];
bool open[N],ans[N];
priority_queue<int> pq[N];

int find(int a){
  if(par[a]==a) return a;
  return par[a]=find(par[a]);
}

void unite(int a,int b){
  a=find(a),b=find(b);
  if(a==b) return;
  if(sz(comp[a])>sz(comp[b])) swap(a,b);
  val[b]+=val[a];
  par[a]=b;
  for(int x:comp[a]) comp[b].push_back(x);
  comp[a].clear();
  while(!pq[a].empty()){
  	pq[b].push(pq[a].top());
  	pq[a].pop();
  }
}

void _(){
  int n,m;
  cin >> n >> m;
  iota(par,par+N,0LL);
  for(int i=1;i<=n;i++) comp[i].push_back(i);
  for(int i=1;i<=n;i++){
  	cin >> s[i];
  	val[i]+=s[i];
  }
  for(int i=1;i<=m;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }

  map<int,vector<int>> lol;
  for(int i=1;i<=n;i++) lol[s[i]].push_back(i);
  for(int i=1;i<=n;i++) for(int x:v[i]) pq[i].push(-s[x]);
  
  for(auto i:lol){
   
    for(int u:i.second) open[u]=1;
    for(int u:i.second){
      for(int x:v[u]){
        if(!open[x]) continue;
        unite(u,x);
      }
    }
    
    vector<int> cur;
    for(int u:i.second) cur.push_back(find(u));
    sort(all(cur));
    cur.erase(unique(all(cur)),cur.end());
    
    for(int u:cur){
     while(!pq[u].empty() && pq[u].top()*-1<=i.first) pq[u].pop();
     if(pq[u].empty()){
      for(int x:comp[u]) ans[x]=1;
      comp[u].clear();
     }
     else if(!pq[u].empty() && pq[u].top()*-1>val[u]){
      for(int x:comp[u]) ans[x]=0;
      comp[u].clear();	
     }
    }
  }

  for(int i=1;i<=n;i++) cout << ans[i];
  cout << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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