Submission #580075

#	Time	Username	Problem	Language	Result	Execution time	Memory
580075		jasmin	Stranded Far From Home (BOI22_island)	C++17	100 / 100	514 ms	82752 KiB

island

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct graph{
    int n;
    vector<vector<int> > adi;
    vector<int> chef;
    vector<int> s;
    vector<set<int> > part;

    graph(int a, vector<int>& size){
        n=a;
        adi.resize(n);
        chef.resize(n);
        iota(chef.begin(), chef.end(), 0);
        s.resize(n);
        part.resize(n);
        for(int i=0; i<n; i++){
            s[i]=size[i];
            part[i].insert(i);
        }
    }

    int find(int a){
        if(chef[a]==a) return a;
        return chef[a]=find(chef[a]);
    }
    bool unite(int a, int b){
        if(find(a)==find(b)){
            return false;
        }
        if(s[find(a)]>s[find(b)]){
            swap(a, b);
        }
        s[find(b)]+=s[find(a)];
        for(auto e: part[find(a)]){
            part[find(b)].insert(e);
        }
        chef[find(a)]=find(b);
        return true;
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<int> size(n);
    vector<pair<int,int> > r(n);
    for(int i=0; i<n; i++){
        cin >> size[i];
        r[i]={size[i], i};
    }
    graph g(n, size);
    sort(r.begin(), r.end());
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        g.adi[a-1].push_back(b-1);
        g.adi[b-1].push_back(a-1);
    }

    vector<int> tin(n);
    vector<bool> ans(n, true);
    for(int i=0; i<n; i++){

        int v=r[i].second;
        tin[v]=i;
        for(auto u: g.adi[v]){
            if(size[u]<=size[v]){

                if(g.s[g.find(u)]<size[v]){
                    for(auto e: g.part[g.find(u)]){
                        ans[e]=false;
                    }
                    g.part[g.find(u)].clear();
                }
                g.unite(u, v);
            }
        }
    }

    for(auto e: ans){
        cout << e;
    }
    cout << "\n";
}

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