Submission #603609

#	Time	Username	Problem	Language	Result	Execution time	Memory
603609		veehz	Stranded Far From Home (BOI22_island)	C++17	10 / 100	499 ms	43364 KiB

island

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m;
vector<ll> par, sz, val, a;
vector<vector<int>> e;
vector<bool> spreadable, inGraph; 
map<int, vector<int>> mp;
void make_sets() {
  par.assign(n, 0);
  iota(par.begin(), par.end(), 0);
  sz.assign(n, 1);
  val = a;
}

int find_set(int a) {
  if (par[a] == a) return a;
  return par[a] = find_set(par[a]);
}

ll set_val(int a) { return val[find_set(a)]; }

void union_set(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a == b) return;
  if (sz[a] < sz[b]) swap(a, b);
  par[a] = b;
  sz[b] += sz[a];
  val[b] += val[a];
}

void make_unspreadable(int u){
  spreadable[u] = false;
  for(int v : e[u]){
    if(!inGraph[v]) continue;
    if(spreadable[v]) make_unspreadable(v);
  }
}

int main() {
  cin >> n >> m;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mp[a[i]].push_back(i);
  }

  make_sets();
  e.resize(n);

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    e[a].push_back(b);
    e[b].push_back(a);
  }

  spreadable.assign(n,true);
  inGraph.assign(n,false);

  for(auto& [num, vec] : mp) {
    for(int& u : vec) {
      for(auto& v : e[u]) {
        if(!inGraph[v]) continue;
        if(set_val(v) < num){
          make_unspreadable(v);
        }
        union_set(u, v);
      }
      inGraph[u] = true;
    }
  }

  for(int i = 0; i < n; i++) {
    cout << int(spreadable[i]);
  }
  cout << endl;
}

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