제출 #1362784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362784		ramzialoulou	Stranded Far From Home (BOI22_island)	C++20	100 / 100	103 ms	31444 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;
int a[N];
int p[N];
int done[N];
int win[N];
int64_t sum[N];
vector<int> g[N];
vector<int> sons[N];

int get(int x) {
  return (x == p[x] ? x : p[x] = get(p[x]));
}

void dfs(int u) {
  win[u] = 1;
  for (int v : sons[u]) {
    dfs(v);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = i;
    sum[i] = a[i];
  }
  while (m--) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 1);
  sort(order.begin(), order.end(), [&](int x, int y) {
    return a[x] < a[y];
  });
  for (int u : order) {
    done[u] = 1;
    for (int v : g[u]) {
      v = get(v);
      if (!done[v] || v == u) continue;
      if (sum[v] >= a[u]) {
        sons[u].push_back(v);
      }
      sum[u] += sum[v];
      p[v] = u;
    }
  }
  dfs(order[n - 1]);
  for (int i = 1; i <= n; i++) {
    cout << win[i];
  }
  return 0;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 10 / 10
• 서브태스크 3: 15 / 15
• 서브태스크 4: 30 / 30
• 서브태스크 5: 35 / 35