oj.uz

Submission #1093008

# Submission time Handle Problem Language Result Execution time Memory
1093008 2024-09-25T17:14:28 Z LittleFlowers__ Stranded Far From Home (BOI22_island) C++17
10 / 100
 278 ms 85404 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define in ({long long x = 0; int c = getchar(), n = 0; for(; !isdigit(c); c = getchar()) n = (c == '-'); for(; isdigit(c); c = getchar()) x = x * 10 + c - '0'; n ? -x : x;})

const int N = 200010;

int n, m;
long long totalWeight[N], weight[N];
struct Edge {
  int u, v;
} edges[N];

int id[N];
set<int> able[N];
int root(int x) {
  return !id[x] ? x : id[x] = root(id[x]);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> weight[i];
    totalWeight[i] = weight[i];
    able[i].insert(i);
  }
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;

    if (weight[u] > weight[v]) swap(u, v);
    edges[i] = { u, v };
  }

  sort(edges + 1, edges + m + 1, [](Edge x, Edge y) {
    return tie(weight[x.u], weight[x.v]) < tie(weight[y.u], weight[y.v]);
    });

  for (int i = 1; i <= m; ++i) {
    auto [u, v] = edges[i];
    auto [x, y] = make_pair(root(u), root(v));
    if (x == y) continue;

    if (able[x].size() < able[y].size()) {
      swap(x, y);
      swap(u, v);
    }

    bool leftAble = false;
    bool rightAble = false;

    if (totalWeight[x] >= totalWeight[y]) leftAble = true;
    if (totalWeight[y] >= totalWeight[x]) rightAble = true;
    if (totalWeight[x] >= weight[v] && able[y].count(v)) leftAble = true;
    if (totalWeight[y] >= weight[u] && able[x].count(u)) rightAble = true;

    if (leftAble && rightAble) {
      able[x].insert(able[y].begin(), able[y].end());
    } else if (leftAble) {

    } else {
      swap(able[x], able[y]);
    }

    id[y] = x;
    totalWeight[x] += totalWeight[y];
  }

  int root = 1;
  while (id[root]) root += 1;

  for (int i = 1; i <= n; ++i) {
    cout << able[root].count(i);
  }
  cout << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 5 ms 10072 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Incorrect 5 ms 9820 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 5 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 116 ms 37808 KB Output is correct
4 Correct 259 ms 82512 KB Output is correct
5 Correct 214 ms 49184 KB Output is correct
6 Correct 189 ms 51280 KB Output is correct
7 Correct 195 ms 51024 KB Output is correct
8 Correct 278 ms 70740 KB Output is correct
9 Correct 151 ms 59728 KB Output is correct
10 Correct 75 ms 28240 KB Output is correct
11 Correct 194 ms 37456 KB Output is correct
12 Correct 151 ms 44756 KB Output is correct
13 Correct 255 ms 85404 KB Output is correct
14 Correct 251 ms 84492 KB Output is correct
15 Correct 149 ms 38736 KB Output is correct
16 Correct 131 ms 37716 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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