oj.uz

Submission #603653

# Submission time Handle Problem Language Result Execution time Memory
603653 2022-07-24T09:24:01 Z veehz Stranded Far From Home (BOI22_island) C++17
10 / 100
 479 ms 39660 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 3 ms 596 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 332 ms 39628 KB Output is correct
4 Correct 257 ms 21904 KB Output is correct
5 Correct 344 ms 38416 KB Output is correct
6 Correct 320 ms 34420 KB Output is correct
7 Correct 347 ms 39660 KB Output is correct
8 Correct 287 ms 18560 KB Output is correct
9 Correct 288 ms 34552 KB Output is correct
10 Correct 299 ms 35296 KB Output is correct
11 Correct 211 ms 19404 KB Output is correct
12 Correct 267 ms 18664 KB Output is correct
13 Correct 240 ms 27840 KB Output is correct
14 Correct 232 ms 26904 KB Output is correct
15 Correct 319 ms 39596 KB Output is correct
16 Correct 246 ms 39200 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 479 ms 39376 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 321 ms 18760 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 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -