Submission #1125254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125254		Mamedov	Stranded Far From Home (BOI22_island)	C++20	100 / 100	138 ms	26748 KiB

island

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


template <typename T> void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << ln;
}

struct DSU {
  vector<int>par;
  vector<vector<int>>group;
  vector<ll>sum;
  string ans;
  int n;
  DSU(int n, vector<int> &val) {
    n = n;
    par.assign(n, -1);
    group.resize(n);
    sum.resize(n);
    for (int i = 0; i < n; ++i) {
      group[i].emplace_back(i);
      sum[i] = val[i];
    }
    ans.assign(n, '1');
  }
  int Find(int v) {
    return (par[v] < 0 ? v : par[v] = Find(par[v]));
  }
  ll getSum(int v) {
    return sum[Find(v)];
  }
  void setAns(int v) {
    v = Find(v);
    for (int u : group[v]) {
      ans[u] = '0';
    }
  }
  void Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      if (par[u] > par[v]) swap(u, v);
      par[u] += par[v];
      par[v] = u;

      sum[u] += sum[v];
      group[u].insert(group[u].end(), all(group[v]));
      group[v].clear();
    }
  }
};
void solve() {
  int n, m;
  cin >> n >> m;
  vi val(n);
  for (int &i : val) {
    cin >> i;
  }
  vector<array<int, 2>>e(m);
  for (int i = 0; i < m; ++i) {
    cin >> e[i][0] >> e[i][1];
    --e[i][0];
    --e[i][1];
    if (val[e[i][0]] > val[e[i][1]]) swap(e[i][0], e[i][1]);
  }
  sort(all(e), [&val](array<int, 2> e1, array<int, 2> e2) {return val[e1[1]] < val[e2[1]];});
  DSU dsu(n, val);
  for (auto [u, v] : e) {
    if (dsu.getSum(u) < val[v]) dsu.setAns(u);
    dsu.Union(u, v);
  }
  cout << dsu.ans << ln;
}
int main() {
  iospeed;
  solve();
  return 0;
}

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