Submission #837605

#	Time	Username	Problem	Language	Result	Execution time	Memory
837605		d4xn	Stranded Far From Home (BOI22_island)	C++17	100 / 100	332 ms	69392 KiB

island

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

#define int long long

const int N = 2e5+5;

int n, m, a[N], p[N], sz[N], dp[N];
vector<int> adj[N];
pair<int, int> s[N];
set<pair<int, int>> st[N];
bitset<N> ok;

int findSet(int x) {
  return p[x] = (p[x] == x ? x : findSet(p[x]));
}

void unite(int x, int y) {
  int X = x;

  x = findSet(x);
  y = findSet(y);
  if (x == y) return;

  if (sz[x] < sz[y]) {
    swap(x, y);
  }

  p[y] = x;
  sz[x] += sz[y];

  for (pair<int, int> z : st[y]) {
    st[x].insert(z);
  }

  while (*st[x].begin() <= make_pair(a[X], X)) st[x].erase(st[x].begin());
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  a[n] = INT_MAX;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    s[i] = make_pair(a[i], i);
  }
  sort(s, s+n);

  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }

  for (int i = 0; i < n; i++) {
    p[i] = i;
    sz[i] = a[i];

    st[i].insert(make_pair(INT_MAX, n));
    for (int& j : adj[i]) {
      if (make_pair(a[j], j) > make_pair(a[i], i)) st[i].insert(make_pair(a[j], j));
    }
  }

  for (int i = 0; i < n; i++) {
    int x = s[i].second;

    for (int& j : adj[x]) {
      if (make_pair(a[j], j) < make_pair(a[x], x)) unite(x, j);
    }

    int y = findSet(x);
    int z = sz[y];
    int nwMn = st[y].begin()->second;

    if (nwMn == n) {
      dp[x] = x;
      ok[x] = 1;
    }
    else if (a[nwMn] <= z) {
      dp[x] = nwMn;
    }
    else {
      dp[x] = x;
    }
  }

  for (int i = n-1; i >= 0; i--) {
    int x = s[i].second;
    ok[x] = ok[dp[x]];
  }

  for (int i = 0; i < n; i++) {
    cout << ok[i];
  }
  cout << "\n";
}

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