제출 #651057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651057		600Mihnea	Stranded Far From Home (BOI22_island)	C++17	100 / 100	322 ms	35572 KiB

island

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int n,m;
  cin>>n>>m;
  vector<ll> s(n);
  vector<int> t(n,-1);
  vector<int> ord(n);
  vector<vector<int>> bosses(n);
  vector<vector<int>> g(n);
  for (int i=0;i<n;i++) {
    cin>>s[i];
    ord[i]=i;
    bosses[i]={i};
  }
  sort(ord.begin(),ord.end(),[&](int i,int j){return s[i]<s[j];});
  for (int i=0;i<m;i++) {
    int a,b;
    cin>>a>>b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  function<int(int)>root=[&](int a){
    if(t[a]==a){
      return a;
    }else{
      return t[a]=root(t[a]);
    }
  };
  function<void(int,int)>join=[&](int a,int b){
    a=root(a);
    b=root(b);
    if(a==b){
      assert(0);
      return;
    }
    if ((int)bosses[a].size()>(int)bosses[b].size()){
      swap(a,b);
    }
    t[a]=b;
    s[b]+=s[a];
    for (auto &boss:bosses[a]){
      bosses[b].push_back(boss);
    }
  };
  for (auto &v:ord){
    /// activate vertex v
    vector<int> comps;
    for (auto &ngh:g[v]){
      if (t[ngh]!=-1){
        comps.push_back(root(ngh));
      }
    }
    sort(comps.begin(),comps.end());
    comps.resize(unique(comps.begin(),comps.end())-comps.begin());
    t[v]=v;
    for (auto &c:comps){
      if (s[c]<s[v]){
        bosses[c].clear();
      }
    }
    for(auto&c:comps){
      join(v,c);
    }
  }
  vector<int> isboss(n,0);
  for (auto &boss:bosses[root(0)]){
    isboss[boss]=1;
  }
  for (auto &is:isboss){
    cout<<is;
  }
  cout<<"\n";
  return 0;
}

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