oj.uz

Submission #721112

# Submission time Handle Problem Language Result Execution time Memory
721112 2023-04-10T10:18:27 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
10 / 100
 735 ms 52296 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);
      map<pair<int, int>, int> answ;
      int tm = 0;
      function<int(int, int)> check = [&](int u, int timer){
        if(answ.find(make_pair(timer, u)) != answ.end()) {
          return answ[make_pair(timer, u)];
        }
        if(ans[u] == '0') return 0;
        if(par[u] == u) return 1;
        int r = check(par[u], timer);
        if(!r) ans[u] = '0';
        answ[make_pair(timer, u)] = r;
        return r;
      };
      function<LL(LL)> get = [&](LL u){
        if(par[u] == u) return u;
        if(!check(u, tm)) 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){
        ++tm;
        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
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 5 ms 980 KB Output is correct
5 Correct 5 ms 772 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Incorrect 4 ms 852 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
10.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 386 ms 47640 KB Output is correct
4 Correct 487 ms 41732 KB Output is correct
5 Correct 431 ms 44388 KB Output is correct
6 Correct 382 ms 40876 KB Output is correct
7 Correct 428 ms 45936 KB Output is correct
8 Correct 597 ms 43020 KB Output is correct
9 Correct 294 ms 39356 KB Output is correct
10 Correct 153 ms 35356 KB Output is correct
11 Correct 289 ms 32644 KB Output is correct
12 Correct 735 ms 39464 KB Output is correct
13 Correct 511 ms 42996 KB Output is correct
14 Correct 470 ms 41708 KB Output is correct
15 Correct 391 ms 51564 KB Output is correct
16 Correct 363 ms 51056 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 Correct 608 ms 52296 KB Output is correct
3 Correct 526 ms 47440 KB Output is correct
4 Correct 446 ms 31760 KB Output is correct
5 Incorrect 486 ms 42880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 648 ms 31780 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 5 ms 980 KB Output is correct
5 Correct 5 ms 772 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Incorrect 4 ms 852 KB Output isn't correct
10 Halted 0 ms 0 KB -