oj.uz

Submission #635747

# Submission time Handle Problem Language Result Execution time Memory
635747 2022-08-26T18:23:33 Z null_awe Stranded Far From Home (BOI22_island) C++14
10 / 100
 329 ms 33056 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;

#define ll long long
#define pii pair<int, int>

const int INF = 1e9;

vector<int> r, p;

int find(int a) { return a == p[a] ? a : p[a] = find(p[a]); }

void link(int a, int b) {
  a = find(a), b = find(b);
  if (a == b) return;
  if (r[a] < r[b]) swap(a, b);
  if (r[a] == r[b]) ++r[a];
  p[b] = a;
}

int main() {
  int n, m; cin >> n >> m;
  vector<int> nodes(n); for (int i = 0; i < n; ++i) cin >> nodes[i];
  vector<pii> arr(n); for (int i = 0; i < n; ++i) arr[i] = {nodes[i], n - i};
  sort(arr.begin(), arr.end()), reverse(arr.begin(), arr.end());
  for (int i = 0; i < n; ++i) arr[i].second = n - arr[i].second;
  vector<int> io(n); for (int i = 0; i < n; ++i) io[arr[i].second] = i;
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b; --a, --b;
    adj[a].push_back(b), adj[b].push_back(a);
  }
  r.resize(n), p.resize(n); for (int i = 0; i < n; ++i) p[i] = i;
  vector<ll> sizes(n), psizes(n);
  for (int i = n - 1; i >= 0; --i) {
    int v = arr[i].second;
    sizes[v] = nodes[v];
    bool bs = false;
    set<int> done;
    for (int u : adj[v]) {
      if (io[u] < io[v] && nodes[u] == nodes[v]) bs = true;
      if (io[u] < io[v] || done.count(find(u))) continue;
      sizes[v] += psizes[find(u)], done.insert(find(u));
    }
    if (!bs) for (int u : adj[v]) if (nodes[u] == nodes[v]) sizes[u] = sizes[v];
    for (int u : adj[v]) if (io[u] > io[v]) link(u, v);
    psizes[find(v)] = sizes[v];
  }
  vector<int> nd(n, INF); nd[arr[0].second] = 0;
  for (int i = 1; i < n; ++i) {
    for (int u : adj[arr[i].second]) {
      if (io[u] > i || nd[u] == INF || nodes[u] > sizes[arr[i].second]) continue;
      nd[arr[i].second] = 0;
    }
  }
  /*
  queue<pii> q; q.push({arr[0].second, -1});
  while (q.size()) {
    int v = q.front().first, from = q.front().second, rn = max(nodes[v], nd[v]); q.pop();
    cout << v << ' ' << nd[v] << '\n';
    for (int u : adj[v]) {
      if (u == from) continue;
      ll need;
      if (nodes[u] >= nodes[v]) need = max(nd[v] - sizes[u] + sizes[v], 0LL);
      else need = max(max(nodes[v] - sizes[u], (ll) nd[v]), 0LL);
      if (need < nd[u]) {
        nd[u] = need;
        q.push({u, v});
      }
    }
  }
  */
  //for (int num : nd) cout << num << '\n';
  for (int i = 0; i < n; ++i) cout << (nd[i] == 0);
  cout << '\n';
  //for (ll sz : sizes) cout << sz << ' ';
  //cout << '\n';
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 3 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 270 ms 20628 KB Output is correct
4 Correct 236 ms 20876 KB Output is correct
5 Correct 276 ms 23688 KB Output is correct
6 Correct 286 ms 24356 KB Output is correct
7 Correct 280 ms 24496 KB Output is correct
8 Correct 278 ms 24456 KB Output is correct
9 Correct 266 ms 24304 KB Output is correct
10 Correct 328 ms 33056 KB Output is correct
11 Correct 329 ms 32772 KB Output is correct
12 Correct 253 ms 23088 KB Output is correct
13 Correct 216 ms 22880 KB Output is correct
14 Correct 234 ms 23108 KB Output is correct
15 Correct 263 ms 24468 KB Output is correct
16 Correct 201 ms 23596 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 309 ms 19880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 325 ms 20020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 3 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -