oj.uz

Submission #721094

# Submission time Handle Problem Language Result Execution time Memory
721094 2023-04-10T10:05:23 Z YENGOYAN Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 39816 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(vis[u] != -1) return vis[u];
        if(ans[u] == '0') return vis[u] = 0;
        if(par[u] == u) return vis[u] = 1;
        return vis[u] = check(par[u]);
      };
      function<LL(LL)> get = [&](LL u){
        if(par[u] == u) return u;
        vis = vector<int> (n, -1);
        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){
        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
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 4 ms 660 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 4 ms 476 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 712 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct

Subtask #2
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 201 ms 39816 KB Output is correct
4 Execution timed out 1084 ms 19940 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1076 ms 39312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1067 ms 19628 KB Time limit exceeded
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 4 ms 660 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 4 ms 476 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 712 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 201 ms 39816 KB Output is correct
18 Execution timed out 1084 ms 19940 KB Time limit exceeded
19 Halted 0 ms 0 KB -