oj.uz

Submission #721072

# Submission time Handle Problem Language Result Execution time Memory
721072 2023-04-10T09:40:06 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
10 / 100
 381 ms 39052 KB 
/*
                                            //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                            \\                                    //
                                            //  271828___182845__904523__53602__  \\
                                            \\  87___47____13______52____66__24_  //
                                            //  97___75____72______47____09___36  \\
                                            \\  999595_____74______96____69___67  //
                                            //  62___77____24______07____66__30_  \\
                                            \\  35___35____47______59____45713__  //
                                            //                                    \\
                                            \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
        */
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>
#include <functional>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;

vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };

void solve() {
  int n, m; cin >> n >> m;
  vector<int> s(n);
  map<int, vector<int>> srt;
  for(int i = 0; i < n; ++i){
    cin >> s[i];
    srt[s[i]].push_back(i);
  }
  vector<int> t = s;
  sort(t.begin(), t.end());
  vector<vector<int>> gp(n);
  for(int i = 0; i < m; ++i){
    int u, v; cin >> u >> v;
    gp[--u].push_back(--v);
    gp[v].push_back(u);
  }
  vector<LL> par(n), sz(n);
  for(int i = 0; i < n; ++i){
    par[i] = i;
    sz[i] = s[i];
  }
  string ans(n, '1');
  function<LL(LL)> get = [&](LL u){
    if(par[u] == u) return u;
    if(ans[par[u]] == '0') ans[u] = '0';
    return par[u] = get(par[u]);
  };
  function<void(int u, int v)> unions = [&](int u, int v){
    int a = get(u), b = get(v);
    if(a == b) return;
    par[b] = a;
    sz[a] += sz[b];
  };
  vector<int> vis(n, -1);
  function<int(int)> check = [&](int u){
    if(vis[u] != -1) return vis[u];
    if(ans[u] == '0') return vis[u] = 0;
    if(par[u] == u) return vis[u] = 1;
    return vis[u] = check(par[u]);
  };
  for(auto x : srt){
    vector<int> nodes = x.second;
    int cnt = x.first;
    for(int &u : nodes){
      for(int &v : gp[u]){
        if(s[v] <= s[u]){
          int p = get(v);
          if(sz[p] < cnt){
            ans[p] = '0';
          }
        }
      }
    }
    for(int &u : nodes) {
      for(int &v : gp[u]){
        if(s[v] <= s[u]){
          unions(u, v);
        }
      }
    }
  }
  for(int i = 0; i < n; ++i){
    cout << check(i);
  }
  cout << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // int t; cin >> t; while (t--)
  solve();

}

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 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Incorrect 1 ms 468 KB Output isn't correct
15 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 206 ms 39024 KB Output is correct
4 Correct 143 ms 19172 KB Output is correct
5 Correct 218 ms 37776 KB Output is correct
6 Correct 199 ms 33880 KB Output is correct
7 Correct 218 ms 39052 KB Output is correct
8 Correct 193 ms 19312 KB Output is correct
9 Correct 182 ms 33912 KB Output is correct
10 Correct 148 ms 34668 KB Output is correct
11 Correct 107 ms 20052 KB Output is correct
12 Correct 171 ms 19208 KB Output is correct
13 Correct 125 ms 19324 KB Output is correct
14 Correct 126 ms 19088 KB Output is correct
15 Correct 190 ms 39024 KB Output is correct
16 Correct 151 ms 38584 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 381 ms 38824 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 198 ms 18188 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 0 ms 212 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Incorrect 1 ms 468 KB Output isn't correct
15 Halted 0 ms 0 KB -