Submission #837539

#	Time	Username	Problem	Language	Result	Execution time	Memory
837539		d4xn	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1006 ms	524288 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];
bitset<N> ok;
set<pair<int, int>> mn[N];

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

void unite(int x, int y) {
  //cerr << "Unite -> " << x+1 << " " << y+1 << endl;

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

  int X = x;

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

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

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

  while (*mn[x].begin() <= make_pair(a[X], X)) mn[x].erase(mn[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];

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

  for (int i = 0; i < n; i++) {
    int x = s[i].second;
    int y = a[x];
    int nwMn = n;
    
    for (int& j : adj[x]) {
      if (make_pair(a[j], j) > make_pair(a[x], x))  {
        if (a[j] < a[nwMn]) {
          nwMn = j;
        }
        continue;
      }

      int z = findSet(j);
      y += sz[z];

      if (mn[z].begin()->second != x && mn[z].begin()->first < a[nwMn]) {
        nwMn = mn[z].begin()->second;
      }
      else {
        auto it = mn[z].begin();
        ++it;
        if (it->first < a[nwMn]) {
          nwMn = it->second;
        }
      }
    }

    //cerr << x+1 << " " << y << " " << nwMn+1 << endl;

    if (nwMn == n) {
      //cerr << "a" << endl;
      dp[x] = x;
      ok[x] = 1;
    }
    else if (a[nwMn] <= y) {
      //cerr << "b" << endl;
      dp[x] = nwMn;
    }
    else {
      //cerr << "c" << endl;
      dp[x] = x;
      ok[x] = 0;
    }

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

  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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35