oj.uz

Submission #797637

# Submission time Handle Problem Language Result Execution time Memory
797637 2023-07-29T17:32:07 Z TB_ Stranded Far From Home (BOI22_island) C++17
35 / 100
 1000 ms 33564 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

ll n, m, val, from, to, w;
vl population;

vvl adj(200001);

int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    cin >> n >> m;
    pii biggestPop = {-1, -1};
    fo(i, n){
        cin >> val;
        population.pb(val);
        biggestPop = max(biggestPop, {val, i});
    }
    fo(i, m){
        cin >> from >> to;
        adj[--from].pb(--to);
        adj[to].pb(from);
    }
    vi ans(n, -1);
    ans[biggestPop.S] = 1;

    vi order;
    fo(i, n) order.pb(i);
    shuffle(all(order), rng);

    vi seen(n, 0);
    for(auto start : order){
        if(ans[start] != -1) continue;
        vi visited;
        set<pl> s = {{0, start}};

        ll currentPop = population[start];
        bool succes = false;
        while(!s.empty()){
            auto res = s.lower_bound({currentPop, INF});
            if(res == s.begin()) break;


            tie(w, to) = *--res;
            s.erase(res);
            if(ans[to] == 1 || currentPop >= biggestPop.F){
                succes = true;
                break;
            }
            if(seen[to]) continue;
            seen[to] = 1;
            visited.pb(to);
            currentPop += w;

            for(auto v : adj[to])
                s.insert({population[v], v});
        }
        if(succes){
            ans[start] = 1;
        }else{
            for(auto v : visited) ans[v] = 0;
        }
        for(auto v : visited) seen[v] = 0;
    }
    fo(i, n) cout << ans[i];

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5164 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5176 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 4 ms 5168 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 5 ms 5076 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 158 ms 18952 KB Output is correct
4 Correct 143 ms 24476 KB Output is correct
5 Correct 154 ms 20492 KB Output is correct
6 Correct 154 ms 20936 KB Output is correct
7 Correct 154 ms 21020 KB Output is correct
8 Correct 175 ms 20988 KB Output is correct
9 Correct 150 ms 22272 KB Output is correct
10 Correct 108 ms 20716 KB Output is correct
11 Correct 77 ms 20548 KB Output is correct
12 Correct 137 ms 19620 KB Output is correct
13 Correct 136 ms 29644 KB Output is correct
14 Correct 126 ms 27684 KB Output is correct
15 Correct 153 ms 20052 KB Output is correct
16 Correct 347 ms 20508 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 142 ms 17704 KB Output is correct
3 Correct 142 ms 20020 KB Output is correct
4 Correct 89 ms 20044 KB Output is correct
5 Correct 107 ms 21216 KB Output is correct
6 Correct 148 ms 20016 KB Output is correct
7 Correct 135 ms 20036 KB Output is correct
8 Correct 133 ms 20104 KB Output is correct
9 Correct 364 ms 21696 KB Output is correct
10 Correct 393 ms 19780 KB Output is correct
11 Correct 98 ms 19928 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 166 ms 18784 KB Output is correct
3 Correct 164 ms 20920 KB Output is correct
4 Correct 154 ms 21124 KB Output is correct
5 Correct 101 ms 21016 KB Output is correct
6 Correct 91 ms 20568 KB Output is correct
7 Execution timed out 1073 ms 33564 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5164 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5176 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 4 ms 5168 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 5 ms 5076 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 158 ms 18952 KB Output is correct
18 Correct 143 ms 24476 KB Output is correct
19 Correct 154 ms 20492 KB Output is correct
20 Correct 154 ms 20936 KB Output is correct
21 Correct 154 ms 21020 KB Output is correct
22 Correct 175 ms 20988 KB Output is correct
23 Correct 150 ms 22272 KB Output is correct
24 Correct 108 ms 20716 KB Output is correct
25 Correct 77 ms 20548 KB Output is correct
26 Correct 137 ms 19620 KB Output is correct
27 Correct 136 ms 29644 KB Output is correct
28 Correct 126 ms 27684 KB Output is correct
29 Correct 153 ms 20052 KB Output is correct
30 Correct 347 ms 20508 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Correct 142 ms 17704 KB Output is correct
33 Correct 142 ms 20020 KB Output is correct
34 Correct 89 ms 20044 KB Output is correct
35 Correct 107 ms 21216 KB Output is correct
36 Correct 148 ms 20016 KB Output is correct
37 Correct 135 ms 20036 KB Output is correct
38 Correct 133 ms 20104 KB Output is correct
39 Correct 364 ms 21696 KB Output is correct
40 Correct 393 ms 19780 KB Output is correct
41 Correct 98 ms 19928 KB Output is correct
42 Correct 2 ms 4948 KB Output is correct
43 Correct 166 ms 18784 KB Output is correct
44 Correct 164 ms 20920 KB Output is correct
45 Correct 154 ms 21124 KB Output is correct
46 Correct 101 ms 21016 KB Output is correct
47 Correct 91 ms 20568 KB Output is correct
48 Execution timed out 1073 ms 33564 KB Time limit exceeded
49 Halted 0 ms 0 KB -