Submission #580164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580164	2022-06-20T16:27:58 Z	Josia	Stranded Far From Home (BOI22_island)	C++14	Compilation error	0 ms	0 KB

island

#pragma GCC optimize("O3")
#pragma GCC target("avx3")
#include <bits/stdc++.h>

using namespace std;

#define int int64_t


struct unionfindElem {
    int chef;
    int amount;
    unordered_set<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(unordered_set<int>& a, unordered_set<int>& b) {
    if (a.size() > b.size()) {
        swap(a, b);
    }
    for (int i: a) b.insert(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;
}

Compilation message

cc1plus: error: attribute 'avx3' argument 'target' is unknown