oj.uz

Submission #837539

# Submission time Handle Problem Language Result Execution time Memory
837539 2023-08-25T12:05:53 Z d4xn Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14448 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Incorrect 20 ms 21400 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14372 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 214 ms 56292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 374 ms 74588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Execution timed out 1006 ms 524288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14448 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Incorrect 20 ms 21400 KB Output isn't correct
5 Halted 0 ms 0 KB -