oj.uz

답안 #721102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721102 2023-04-10T10:08:54 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
0 / 100
 382 ms 39420 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');
      vector<int> vis(n, -1);
      function<int(int)> check = [&](int u){
        if(ans[u] == '0') return 0;
        if(par[u] == u) return 1;
        return check(par[u]);
      };
      function<LL(LL)> get = [&](LL u){
        if(par[u] == u) return u;
        if(!check(u)) 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];
      };
      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(v, u);
            }
          }
        }
      }
      vis = vector<int> (n, -1);
      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

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 382 ms 39420 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 230 ms 18932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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