Submission #1309016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309016		cowkim	Stranded Far From Home (BOI22_island)	C++20	0 / 100	306 ms	41432 KiB

island

#include <bits/stdc++.h>
using namespace std;
struct stl{
    int nrEl;
    vector<int> possible;
    vector<int> members;
    stl(int x, int ppl){
        nrEl = ppl;
        possible = {x};
        members = {x};
    }
};
void merge(stl* a, stl* b,vector<stl*>& stlp){
    if(a == b) return;
    if(a->members.size() < b->members.size()) swap(a,b);
    if(b->possible.size() > 0){
        //cout << b->possible.size() << " " << b->possible[0] << endl;
        for(auto possible : b->possible){
            a->possible.push_back(possible);
        }
    }
    for(auto member : b->members){
        stlp[member] = a;
        a->members.push_back(member);
    }
    a->nrEl += b->nrEl;
    delete(b);
}
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> nrPpl(n);
    for(int i = 0; i < n; i++){
        cin >> nrPpl[i];
    }
    vector<stl*> stlp(n,nullptr);
    for(int i = 0; i< n; i++){
        stlp[i] = new stl(i,nrPpl[i]);
    }
    vector<pair<int,int>> sortedNodes(n);
    for(int i = 0; i< n; i++){
        sortedNodes[i] = {nrPpl[i],i};
    }
    sort(sortedNodes.begin(),sortedNodes.end());
    vector<vector<int>> adj(n);
    for(int i = 0; i< m; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(auto par : sortedNodes){
        int node = par.second;
        for(auto child : adj[node]){
            if(nrPpl[child] > nrPpl[node]) continue;
            if(stlp[child]->nrEl < nrPpl[node]){
                //cout << child << " cant break through " << node << endl;
                stlp[child]->possible.clear();
            }
            merge(stlp[child],stlp[node],stlp);
        }
    }
    vector<bool> possible(n,false);
    for(auto num : stlp[0]->possible){
        possible[num] = true;
    }
    for(int i = 0; i< n; i++) cout << possible[i];
    cout << endl;
    return 0;
}

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