oj.uz

Submission #721105

# Submission time Handle Problem Language Result Execution time Memory
721105 2023-04-10T10:10:43 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 39660 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(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.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 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 234 ms 39656 KB Output is correct
4 Correct 156 ms 19104 KB Output is correct
5 Correct 219 ms 38500 KB Output is correct
6 Correct 213 ms 34412 KB Output is correct
7 Correct 223 ms 39648 KB Output is correct
8 Correct 164 ms 19324 KB Output is correct
9 Correct 227 ms 34416 KB Output is correct
10 Correct 156 ms 35316 KB Output is correct
11 Correct 125 ms 20048 KB Output is correct
12 Correct 195 ms 19216 KB Output is correct
13 Correct 135 ms 19324 KB Output is correct
14 Correct 154 ms 19160 KB Output is correct
15 Correct 208 ms 39640 KB Output is correct
16 Correct 189 ms 39240 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 401 ms 39396 KB Output is correct
3 Correct 335 ms 34548 KB Output is correct
4 Correct 151 ms 19280 KB Output is correct
5 Correct 161 ms 19360 KB Output is correct
6 Correct 432 ms 39660 KB Output is correct
7 Correct 233 ms 39644 KB Output is correct
8 Correct 231 ms 39636 KB Output is correct
9 Correct 151 ms 39296 KB Output is correct
10 Execution timed out 1090 ms 31464 KB Time limit exceeded
11 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 Correct 298 ms 18776 KB Output is correct
3 Correct 254 ms 18756 KB Output is correct
4 Correct 230 ms 18880 KB Output is correct
5 Correct 224 ms 19272 KB Output is correct
6 Correct 203 ms 18472 KB Output is correct
7 Execution timed out 1085 ms 21264 KB Time limit exceeded
8 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 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 234 ms 39656 KB Output is correct
18 Correct 156 ms 19104 KB Output is correct
19 Correct 219 ms 38500 KB Output is correct
20 Correct 213 ms 34412 KB Output is correct
21 Correct 223 ms 39648 KB Output is correct
22 Correct 164 ms 19324 KB Output is correct
23 Correct 227 ms 34416 KB Output is correct
24 Correct 156 ms 35316 KB Output is correct
25 Correct 125 ms 20048 KB Output is correct
26 Correct 195 ms 19216 KB Output is correct
27 Correct 135 ms 19324 KB Output is correct
28 Correct 154 ms 19160 KB Output is correct
29 Correct 208 ms 39640 KB Output is correct
30 Correct 189 ms 39240 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 401 ms 39396 KB Output is correct
33 Correct 335 ms 34548 KB Output is correct
34 Correct 151 ms 19280 KB Output is correct
35 Correct 161 ms 19360 KB Output is correct
36 Correct 432 ms 39660 KB Output is correct
37 Correct 233 ms 39644 KB Output is correct
38 Correct 231 ms 39636 KB Output is correct
39 Correct 151 ms 39296 KB Output is correct
40 Execution timed out 1090 ms 31464 KB Time limit exceeded
41 Halted 0 ms 0 KB -