제출 #721054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721054		YENGOYAN	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1075 ms	50152 KiB

island

/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  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);
  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]);
  };
  vector<vector<int>> new_gp(n);
  function<void(int)> dfs = [&](int u) {
    // if(vis[u] != -1) return;
    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){
//          ans[p] = '0';
          dfs(p);
        }
      }
    }
    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 << check(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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35