oj.uz

답안 #603703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603703 2022-07-24T09:58:05 Z veehz Stranded Far From Home (BOI22_island) C++17
10 / 100
 484 ms 40748 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

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

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

void union_set(ll a, ll 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(ll& 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 (ll i = 0; i < n; i++) {
    cin >> a[i];
    mp[a[i]].push_back(i);
  }

  make_sets();
  e.resize(n);

  for (ll i = 0; i < m; i++) {
    ll 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(ll i = 0; i < n; i++) {
    cout << ll(spreadable[i]);
  }
  cout << endl;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 320 ms 40644 KB Output is correct
4 Correct 240 ms 23724 KB Output is correct
5 Correct 308 ms 39380 KB Output is correct
6 Correct 299 ms 35660 KB Output is correct
7 Correct 366 ms 40748 KB Output is correct
8 Correct 257 ms 20356 KB Output is correct
9 Correct 303 ms 37140 KB Output is correct
10 Correct 237 ms 36348 KB Output is correct
11 Correct 190 ms 20796 KB Output is correct
12 Correct 255 ms 20340 KB Output is correct
13 Correct 230 ms 28724 KB Output is correct
14 Correct 234 ms 27712 KB Output is correct
15 Correct 307 ms 39648 KB Output is correct
16 Correct 240 ms 39244 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 484 ms 39328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 292 ms 20436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -