Submission #654580

#	Time	Username	Problem	Language	Result	Execution time	Memory
654580		atigun	Stranded Far From Home (BOI22_island)	C++14	100 / 100	298 ms	37996 KiB

island

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

struct dsu{
  vector<int> parent;
  vector<ll> sum;
  vector<vector<int>> S;
  int n;
  dsu(int dsu_size) : n(dsu_size){
    parent.resize(n+5);
    iota(parent.begin(), parent.end(), 0);
    sum.resize(n+5, 0);
    S.resize(n+5);
  }
  int find(int v){
    return parent[v] = (parent[v] == v ? v : find(parent[v]));
  }
  void merge(int v, int u){
    if(S[find(u)].size() > S[find(v)].size())
      swap(u, v);
    if(find(u) == find(v))
      return;
    for(int x : S[find(u)])
      S[find(v)].push_back(x);
    S[find(u)].clear();
    sum[find(v)]+= sum[find(u)];
    parent[find(u)] = parent[find(v)];
  }
  ll comp_sum(int v){
    return sum[find(v)];
  }
};

const int maxn = 2e5;

int n, m;
dsu dsu(maxn+5);
vector<ll> a(maxn+5);
vector<vector<int>> g(maxn+5), new_g(maxn+5);
vector<bool> added(maxn+5), bad(maxn+5), vis(maxn+5);

void solve(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
    dsu.sum[dsu.find(i)] = a[i];
    dsu.S[dsu.find(i)] = {i};
  }
  for(int i = 0; i < m; i++){
    int v, u;
    cin >> v >> u;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  vector<pair<int, int>> query;
  query.reserve(n);
  for(int i = 1; i <= n; i++)
    query.push_back({a[i], i});
  sort(query.begin(), query.end());
  for(int i = 0; i < n; i++){
    int v = query[i].second;
    // cout << v << ": ";
    for(int u : g[v]){
      if(make_pair(a[u], u) < make_pair(a[v], v)){
        // cout << dsu.comp_sum(u) << "\n";
        if(dsu.comp_sum(u) < a[v]){
          dsu.S[dsu.find(u)].clear();
        }
      }
    }
    for(int u : g[v])
      if(make_pair(a[u], u) < make_pair(a[v], v))
        dsu.merge(u, v);
  }
  vector<bool> ans(n+5, 0);
  for(int x : dsu.S[dsu.find(n)])
    ans[x] = 1;
  for(int i = 1; i <= n; i++)
    cout << ans[i];
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while(tt--){
    solve();
  }
}

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