oj.uz

Submission #580124

# Submission time Handle Problem Language Result Execution time Memory
580124 2022-06-20T15:50:09 Z kamelfanger83 Stranded Far From Home (BOI22_island) C++17
0 / 100
 536 ms 60536 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define int long long

using namespace std;

signed main(){
    int n, m; cin >> n >> m;
    vector<int> inh;
    vector<vector<int>> cons (n);
    int s;
    for (int reader = 0; reader < n; ++reader) {
        cin >> s;
        inh.push_back(s);
    }
    int a, b;
    for (int reader = 0; reader < m; ++reader) {
        cin >> a >> b; a--; b--;
        cons[a].push_back(b);
        cons[b].push_back(a);
    }

    //vector<bool> rall (n);????????????????
    vector<bool> poss; poss.resize(n, true);
    vector<int> group (n); for(int i = 0; i < n; i++) group[i] = i;
    vector<int> sum = inh;
    vector<set<int>> in (n); for(int i = 0; i < n; i++) in[i].insert(i);

    auto get = [&](int u){
        int s = u;
        while(group[u] != u) u = group[u];
        while(group[s] != s){
            int beg = group[s];
            group[s] = u;
            s = group[beg];
        }
        return u;
    };

    auto unite = [&](int u, int v){
        u = get(u); v = get(v);
        if(in[u].size() < in[v].size()) swap(u, v);
        group[v] = u;
        sum[u] += sum[v];
        for(int ins : in[v]) in[u].insert(ins);
    };

    vector<int> scanl (n); for (int i = 0; i < n; ++i) scanl[i] = i;

    auto compinh = [&](int r, int s) {return inh[r] < inh[s];};

    sort(scanl.begin(), scanl.end(), compinh);

    for (int scanner : scanl) {
        for(int c : cons[scanner]){
            if(inh[c] <= inh[scanner]){
                if(sum[get(c)] < inh[scanner]){
                    for(int killer : in[get(c)]) poss[killer] = false;
                    in[get(c)].clear();
                }
                unite(c, scanner);
            }
        }
    }

    for(bool printr : poss) cout << printr;

    return 0;
}

Subtask #1
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 0 ms 212 KB Output is correct
4 Incorrect 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 327 ms 43476 KB Output is correct
4 Incorrect 429 ms 41044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 536 ms 60488 KB Output is correct
3 Incorrect 485 ms 60536 KB Output isn't correct
4 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 Incorrect 510 ms 41628 KB Output isn't correct
3 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -