oj.uz

Submission #721124

# Submission time Handle Problem Language Result Execution time Memory
721124 2023-04-10T10:28:36 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
25 / 100
 991 ms 64148 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){
        vector<int> nodes = x.second;
        int cnt = x.first;
        for(int &u : nodes){
          for(int &v : gp[u]){
            if(s[v] <= s[u]){
              ++tm;
              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 1 ms 212 KB Output is correct
2 Correct 1 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 4 ms 852 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Incorrect 3 ms 724 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 377 ms 47612 KB Output is correct
4 Correct 470 ms 41812 KB Output is correct
5 Correct 370 ms 44360 KB Output is correct
6 Correct 412 ms 40780 KB Output is correct
7 Correct 404 ms 45872 KB Output is correct
8 Correct 599 ms 43040 KB Output is correct
9 Correct 350 ms 39356 KB Output is correct
10 Correct 152 ms 35212 KB Output is correct
11 Correct 274 ms 32612 KB Output is correct
12 Correct 639 ms 39388 KB Output is correct
13 Correct 457 ms 42884 KB Output is correct
14 Correct 494 ms 41788 KB Output is correct
15 Correct 416 ms 51568 KB Output is correct
16 Correct 340 ms 50988 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 508 ms 52796 KB Output is correct
3 Correct 535 ms 48248 KB Output is correct
4 Correct 409 ms 31800 KB Output is correct
5 Correct 454 ms 43008 KB Output is correct
6 Correct 550 ms 53208 KB Output is correct
7 Correct 586 ms 64056 KB Output is correct
8 Correct 563 ms 64148 KB Output is correct
9 Correct 352 ms 51012 KB Output is correct
10 Correct 297 ms 46220 KB Output is correct
11 Correct 327 ms 41672 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 628 ms 36688 KB Output is correct
3 Correct 515 ms 36444 KB Output is correct
4 Correct 599 ms 38880 KB Output is correct
5 Correct 877 ms 31752 KB Output is correct
6 Correct 879 ms 30280 KB Output is correct
7 Correct 650 ms 45608 KB Output is correct
8 Correct 467 ms 57264 KB Output is correct
9 Correct 543 ms 38388 KB Output is correct
10 Incorrect 991 ms 45880 KB Output isn't correct
11 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 1 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 4 ms 852 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Incorrect 3 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -