Submission #721113

#	Time	Username	Problem	Language	Result	Execution time	Memory
721113		YENGOYAN	Stranded Far From Home (BOI22_island)	C++17	20 / 100	1070 ms	39700 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;
          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;
            int r = check(par[u]);
            if(!r) ans[u] = '0';
            return r;
          };
          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(u, v);
                }
              }
            }
          }
          vis = vector<int> (n, -1);
          for(int i = 0; i < n; ++i){
            get(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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35