oj.uz

Submission #603609

# Submission time Handle Problem Language Result Execution time Memory
603609 2022-07-24T08:52:02 Z veehz Stranded Far From Home (BOI22_island) C++17
10 / 100
 499 ms 43364 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<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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 377 ms 41772 KB Output is correct
4 Correct 237 ms 23572 KB Output is correct
5 Correct 345 ms 39960 KB Output is correct
6 Correct 309 ms 36428 KB Output is correct
7 Correct 379 ms 42444 KB Output is correct
8 Correct 285 ms 21180 KB Output is correct
9 Correct 375 ms 36832 KB Output is correct
10 Correct 257 ms 38296 KB Output is correct
11 Correct 273 ms 22328 KB Output is correct
12 Correct 284 ms 20592 KB Output is correct
13 Correct 241 ms 29260 KB Output is correct
14 Correct 245 ms 29508 KB Output is correct
15 Correct 317 ms 43364 KB Output is correct
16 Correct 295 ms 41860 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Incorrect 499 ms 42788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 316 ms 21856 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 3 ms 560 KB Output isn't correct
5 Halted 0 ms 0 KB -