oj.uz

Submission #721058

# Submission time Handle Problem Language Result Execution time Memory
721058 2023-04-10T09:23:54 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 50076 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;
  vector<pair<int, int>> vp;
  for(int i = 0; i < n; ++i){
    cin >> s[i];
    srt[s[i]].push_back(i);
    vp.push_back({s[i], i});
  }
  sort(vp.begin(), vp.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<int(int)> get = [&](int u){
    if(par[u] == u) return u;
    return 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<bool> vis(n);
  vector<vector<int>> new_gp(n);
  function<void(int)> dfs = [&](int u) {
    vis[u] = 1;
    ans[u] = '0';
    for(int &v : new_gp[u]) {
      if(!vis[v]){
        dfs(v);
      }
    }
  };
  for(int i = 0; i < n; ++i){
    int cnt = vp[i].first, u = vp[i].second;
    for(int &v : gp[u]){
      if(s[v] <= s[u]){
        int p = get(v);
        if(sz[p] < cnt){
          dfs(v);
        }
      }
    }
    for(int &v : gp[u]){
      if(s[v] <= s[u]){
        new_gp[v].push_back(u);
        new_gp[u].push_back(v);
        unions(u, v);
      }
    }
  }
  for(int i = 0; i < n; ++i){
    cout << ans[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 1 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 4 ms 724 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 1 ms 212 KB Output is correct
3 Correct 219 ms 50028 KB Output is correct
4 Correct 197 ms 34236 KB Output is correct
5 Correct 239 ms 48500 KB Output is correct
6 Correct 262 ms 44848 KB Output is correct
7 Correct 259 ms 50076 KB Output is correct
8 Correct 252 ms 29888 KB Output is correct
9 Correct 189 ms 44808 KB Output is correct
10 Correct 182 ms 46396 KB Output is correct
11 Correct 188 ms 32344 KB Output is correct
12 Correct 273 ms 29956 KB Output is correct
13 Correct 211 ms 41420 KB Output is correct
14 Correct 172 ms 40132 KB Output is correct
15 Correct 205 ms 50052 KB Output is correct
16 Correct 170 ms 49464 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 438 ms 49648 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 Execution timed out 1061 ms 29200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 0 ms 212 KB Output is correct
4 Incorrect 4 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -