Submission #580098

#	Time	Username	Problem	Language	Result	Execution time	Memory
580098		kamelfanger83	Stranded Far From Home (BOI22_island)	C++14	0 / 100	359 ms	33404 KiB

island

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int 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]) unite(c, scanner);
                else{
                    for(int killer : in[get(c)]) poss[killer] = false;
                    in[get(c)].clear();
                }
            }
        }
    }

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

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35