Submission #650692

#	Time	Username	Problem	Language	Result	Execution time	Memory
650692		tvladm2009	Stranded Far From Home (BOI22_island)	C++14	100 / 100	238 ms	35780 KiB

island

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2 * 1e5 + 7;
int w[N];
vector<int> g[N], neighbours[N];
int parent[N], order[N];
bool visited[N], ans[N];
ll sum[N];

int getRoot(int u) {
  if (parent[u] == 0) {
    return u;
  }
  return parent[u] = getRoot(parent[u]);
}

void dfs(int u, int p = -1) {
  ans[u] = true;
  for (auto &v : neighbours[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    order[i] = i;
  }
  sort(order + 1, order + n + 1, [&](int x, int y) -> bool {
    return w[x] < w[y];
  });
  for (int i = 1; i <= n; i++) {
    sum[i] = w[i];
  }

  for (int i = 1; i <= n; i++) {
    int u = order[i];
    visited[u] = true;
    for (auto v : g[u]) {
      if (visited[v] == true) {
        v = getRoot(v);
        if (v != u) {
          if (sum[v] >= w[u]) {
            neighbours[u].push_back(v);
          }
          parent[v] = u;
          sum[u] += sum[v];
        }
      }
    }
  }
  dfs(order[n]);
  for (int i = 1; i <= n; i++) {
    cout << ans[i];
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35