oj.uz

Submission #603648

# Submission time Handle Problem Language Result Execution time Memory
603648 2022-07-24T09:21:49 Z veehz Stranded Far From Home (BOI22_island) C++17
0 / 100
 498 ms 39636 KB 
#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<ll, 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(auto& 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(auto& 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.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 240 KB Output is correct
3 Incorrect 377 ms 39636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 498 ms 39440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 306 ms 18696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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