Submission #651058

#	Time	Username	Problem	Language	Result	Execution time	Memory
651058		600Mihnea	Stranded Far From Home (BOI22_island)	C++17	100 / 100	260 ms	31296 KiB

island

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<ll> s(n);
  vector<int> t(n, -1);
  vector<int> ord(n);
  vector<vector<int>> bosses(n);
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    ord[i] = i;
    bosses[i] = { i };
  }
  sort(ord.begin(), ord.end(), [&](int i, int j) {return s[i] < s[j]; });
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  function<int(int)>root = [&](int a) {
    if (t[a] == a) {
      return a;
    }
    else {
      return t[a] = root(t[a]);
    }
  };
  function<void(int, int)>join = [&](int a, int b) {
    a = root(a);
    b = root(b);
    if ((int)bosses[a].size() > (int)bosses[b].size()) {
      swap(a, b);
    }
    t[a] = b;
    s[b] += s[a];
    for (auto& boss : bosses[a]) {
      bosses[b].push_back(boss);
    }
  };
  for (auto& v : ord) {
    /// activate vertex v
    vector<int> comps;
    for (auto& ngh : g[v]) {
      if (t[ngh] != -1) {
        comps.push_back(root(ngh));
      }
    }
    sort(comps.begin(), comps.end());
    comps.resize(unique(comps.begin(), comps.end()) - comps.begin());
    t[v] = v;
    for (auto& c : comps) {
      if (s[c] < s[v]) {
        bosses[c].clear();
      }
    }
    for (auto& c : comps) {
      join(v, c);
    }
  }
  vector<int> isboss(n, 0);
  for (auto& boss : bosses[root(0)]) {
    isboss[boss] = 1;
  }
  for (auto& is : isboss) {
    cout << is;
  }
  cout << "\n";
  return 0;
}

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