oj.uz

Submission #837606

# Submission time Handle Problem Language Result Execution time Memory
837606 2023-08-25T12:45:14 Z d4xn Stranded Far From Home (BOI22_island) C++17
25 / 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];
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 (st[x].size() < st[y].size()) {
    swap(x, 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 20 ms 21392 KB Output is correct
5 Correct 9 ms 15524 KB Output is correct
6 Correct 24 ms 22316 KB Output is correct
7 Correct 21 ms 21808 KB Output is correct
8 Correct 20 ms 21716 KB Output is correct
9 Correct 111 ms 77420 KB Output is correct
10 Correct 8 ms 14932 KB Output is correct
11 Correct 8 ms 14932 KB Output is correct
12 Correct 8 ms 14888 KB Output is correct
13 Correct 8 ms 14936 KB Output is correct
14 Correct 10 ms 15368 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14452 KB Output is correct
3 Correct 152 ms 56228 KB Output is correct
4 Correct 199 ms 87320 KB Output is correct
5 Correct 186 ms 54884 KB Output is correct
6 Correct 204 ms 56328 KB Output is correct
7 Correct 206 ms 56340 KB Output is correct
8 Runtime error 863 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 248 ms 67540 KB Output is correct
3 Correct 254 ms 67836 KB Output is correct
4 Correct 157 ms 55244 KB Output is correct
5 Correct 141 ms 60064 KB Output is correct
6 Correct 261 ms 67824 KB Output is correct
7 Correct 176 ms 67844 KB Output is correct
8 Correct 184 ms 67804 KB Output is correct
9 Correct 102 ms 54820 KB Output is correct
10 Correct 184 ms 68964 KB Output is correct
11 Correct 197 ms 68172 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Execution timed out 1010 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 6 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 20 ms 21392 KB Output is correct
5 Correct 9 ms 15524 KB Output is correct
6 Correct 24 ms 22316 KB Output is correct
7 Correct 21 ms 21808 KB Output is correct
8 Correct 20 ms 21716 KB Output is correct
9 Correct 111 ms 77420 KB Output is correct
10 Correct 8 ms 14932 KB Output is correct
11 Correct 8 ms 14932 KB Output is correct
12 Correct 8 ms 14888 KB Output is correct
13 Correct 8 ms 14936 KB Output is correct
14 Correct 10 ms 15368 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14452 KB Output is correct
17 Correct 152 ms 56228 KB Output is correct
18 Correct 199 ms 87320 KB Output is correct
19 Correct 186 ms 54884 KB Output is correct
20 Correct 204 ms 56328 KB Output is correct
21 Correct 206 ms 56340 KB Output is correct
22 Runtime error 863 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -