oj.uz

Submission #1093145

# Submission time Handle Problem Language Result Execution time Memory
1093145 2024-09-26T03:14:14 Z juicy Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 524292 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, m;
int a[N], pr[N];
long long s[N];
bool lose[N];

int find(int u) {
  if (u == pr[u]) {
    return u;
  }
  int p = find(pr[u]);
  lose[u] |= lose[pr[u]];
  return p;
}

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

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pr[i] = i, s[i] = a[i];
  }
  vector<array<int, 2>> e;
  while (m--) {
    int x, y; cin >> x >> y;
    if (a[x] > a[y]) {
      swap(x, y);
    }
    e.push_back({x, y});
  }
  sort(e.begin(), e.end(), [&](auto i, auto j) {
    return a[i[1]] < a[j[1]];
  });
  for (auto [u, v] : e) {
    u = find(u);
    if (u ^ v) {
      lose[u] = s[u] < a[v];
      pr[u] = v;
      s[v] += s[u];
    }
  }
  for (int i = 1; i <= n; ++i) {
    find(i);
    cout << (lose[i] ? 0 : 1);
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Runtime error 444 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1088 ms 9980 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 86 ms 9868 KB Output is correct
3 Correct 89 ms 9864 KB Output is correct
4 Correct 743 ms 10140 KB Output is correct
5 Correct 436 ms 8452 KB Output is correct
6 Correct 86 ms 9980 KB Output is correct
7 Execution timed out 1090 ms 10264 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 387 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 2 ms 360 KB Output is correct
6 Runtime error 444 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -