Submission #580167

#	Time	Username	Problem	Language	Result	Execution time	Memory
580167		Josia	Stranded Far From Home (BOI22_island)	C++14	100 / 100	855 ms	45460 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define int int64_t


struct unionfindElem {
    int chef;
    int amount;
    vector<int> active;
};

bool compare(unionfindElem A, unionfindElem B) {
    tuple<int, int> a = {A.chef, A.amount};
    tuple<int, int> b = {B.chef, B.amount};
    return a<b;
}



vector<unionfindElem> chefs;

void init(vector<pair<int, int>> vilages) {
    for (pair<int, int> i: vilages) {
        chefs.push_back({i.second, i.first, {i.second}});
    }
    sort(chefs.begin(), chefs.end(), compare);
}


int find(int x) {
    if (chefs[x].chef == x) return x;
    return chefs[x].chef = find(chefs[x].chef);
}


void Merge(vector<int>& a, vector<int>& b) {
    if (a.size() > b.size()) {
        swap(a, b);
    }
    for (int i: a) b.push_back(i);
}


void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;

    chefs[a].chef = b;
    chefs[b].amount += chefs[a].amount;
    Merge(chefs[a].active, chefs[b].active);
}



signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n; int m; cin >> n >> m;

    vector<pair<int, int>> vilages(n);
    vector<int> inhabitants(n);

    for (int i = 0; i<n; i++) {
        cin >> vilages[i].first;
        inhabitants[i] = vilages[i].first;
        vilages[i].second = i;
    }

    sort(vilages.begin(), vilages.end());

    vector<vector<int>> graph(n);

    for (int i = 0; i<m; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    init(vilages);


    vector<int> newcomers;
    for (auto pii: vilages) {
        int i = pii.second;
        newcomers.push_back(i);
        
        for (int j: graph[i]) {
            if (inhabitants[i] > chefs[find(j)].amount) chefs[find(j)].active.clear();
            if (inhabitants[i] >= inhabitants[j]) unite(i, j);
        }
        // for (auto chef: chefs) {
        //     for (int i: chef.active) cerr << i << " ";
        //     cerr << "\n";
        //     cerr << chef.chef << " " << chef.amount << "\n";
        // }
        // cerr << "\n";
    }

    vector<int> res(n);

    auto chef = chefs[find(0)];
    for (int i: chef.active) res[i] = 1;

    for (int i: res) cout << i;
    cout << "\n";


    return 0;
}

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