Submission #1016454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016454		asdfgrace	Stranded Far From Home (BOI22_island)	C++17	100 / 100	143 ms	36548 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&] (int x, int y) {
    return a[x] < a[y];
  });
  vector<int> at(n);
  for (int i = 0; i < n; i++) {
    at[ord[i]] = i;
  }
  vector<vector<int>> edges(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    x = at[x]; y = at[y];
    if (x > y) swap(x, y);
    edges[y].push_back(x);
  }
  vector<int> g(n), sz(n, 1);
  iota(g.begin(), g.end(), 0);
  vector<vector<int>> in(n);
  vector<long long> sum(n);
  for (int i = 0; i < n; i++) {
    in[i].push_back(i);
    sum[i] = a[ord[i]];
  }
  function<int(int)> rep = [&] (int node) {
    while (node != g[node]) node = g[g[node]];
    return node;
  };
  function<void(int, int)> merge = [&] (int x, int y) {
    x = rep(x); y = rep(y);
    if (x == y) return;
    if (sz[y] > sz[x]) swap(x, y);
    g[y] = x;
    sz[x] += sz[y];
    sum[x] += sum[y];
    for (auto i : in[y]) {
      in[x].push_back(i);
    }
    in[y].clear();
  };
  for (int i = 0; i < n; i++) {
    sort(edges[i].begin(), edges[i].end(), [&] (int x, int y) {
      return sum[rep(x)] < sum[rep(y)];
    });
    for (auto j : edges[i]) {
      int ri = rep(i), rj = rep(j);
      if (ri == rj) continue;
      if (a[ord[i]] > sum[rj]) {
        in[rj].clear();
      }
      merge(ri, rj);
    }
  }
  vector<bool> ok(n, false);
  for (int i = 0; i < n; i++) {
    if (sz[i] == n) {
      for (auto j : in[i]) {
        ok[ord[j]] = true;
      }
      break;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << (ok[i] ? '1' : '0');
  }
  cout << '\n';
}

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