Submission #580065

#	Time	Username	Problem	Language	Result	Execution time	Memory
580065		jasmin	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1089 ms	23184 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<int> time;

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

    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;
        }
        s[find(a)]+=s[find(b)];
        chef[find(b)]=find(a);
        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]){
                    g.time[g.find(u)]=i;
                    for(int j=0; j<n; j++){
                        if(g.find(j)==g.find(u)){
                            ans[j]=false;
                        }
                    }
                }
                g.unite(u, v);
            }
        }
    }

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

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