Submission #1093021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093021		LittleFlowers__	Stranded Far From Home (BOI22_island)	C++17	100 / 100	305 ms	89176 KiB

island

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#elif LOCAL
#define debug(...) 42
#endif

#define in ({long long x = 0; int c = getchar(), n = 0; for(; !isdigit(c); c = getchar()) n = (c == '-'); for(; isdigit(c); c = getchar()) x = x * 10 + c - '0'; n ? -x : x;})

const int N = 200010;

int n, m;
long long totalWeight[N], weight[N], maxWeight[N];
struct Edge {
  int u, v;
} edges[N];

int id[N];
set<int> able[N];
int root(int x) {
  return !id[x] ? x : id[x] = root(id[x]);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> weight[i];
    maxWeight[i] = totalWeight[i] = weight[i];
    able[i].insert(i);
  }
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;

    if (weight[u] > weight[v]) swap(u, v);
    edges[i] = { u, v };
  }

  sort(edges + 1, edges + m + 1, [](Edge x, Edge y) {
    return weight[x.v] < weight[y.v];
  });

  for (int i = 1; i <= m; ++i) {
    auto [u, v] = edges[i];
    auto [x, y] = make_pair(root(u), root(v));
    if (x == y) continue;

    if (able[x].size() < able[y].size()) {
      swap(x, y);
      swap(u, v);
    }

    bool leftAble = false;
    bool rightAble = false;

    if (totalWeight[x] >= totalWeight[y]) leftAble = true;
    if (totalWeight[y] >= totalWeight[x]) rightAble = true;
    if (totalWeight[x] >= weight[v] && able[y].count(v)) leftAble = true;
    if (totalWeight[y] >= weight[u] && able[x].count(u)) rightAble = true;
    if (maxWeight[x] >= maxWeight[y]) leftAble = true;
    if (maxWeight[y] >= maxWeight[x]) rightAble = true;

    if (leftAble && rightAble) {
      able[x].insert(able[y].begin(), able[y].end());
    } else if (leftAble) {

    } else {
      swap(able[x], able[y]);
    }

    id[y] = x;
    totalWeight[x] += totalWeight[y];
    maxWeight[x] = max(maxWeight[x], maxWeight[y]);
  }

  int root = 1;
  while (id[root]) root += 1;

  for (int i = 1; i <= n; ++i) {
    cout << able[root].count(i);
  }
  cout << '\n';
}

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