Submission #1202286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202286		Unforgettablepl	Stranded Far From Home (BOI22_island)	C++20	100 / 100	490 ms	85780 KiB

island

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

#define int long long

struct UFDS{
    vector<int> siz,s,p;
    vector<set<int>> activenodes;
    set<pair<int,int>> ses;
    UFDS(int N,vector<int> s):s(s),siz(N+1,1),p(N+1),activenodes(N+1){
        for(int i=1;i<=N;i++){
            p[i]=i;
            activenodes[i].emplace(i);
        }
    }
    void activate(int x){
        ses.emplace(s[x],x);
    }
    int findRoot(int x){
        return p[x]==x ? x : findRoot(p[x]);
    }
    void unite(int a,int b){
        a = findRoot(a);
        b = findRoot(b);
        if(a==b)return;
        if(siz[b]>siz[a])swap(a,b);
        ses.erase({s[a],a});
        ses.erase({s[b],b});
        s[a]+=s[b];
        p[b]=a;
        siz[a]+=siz[b];
        ses.emplace(s[a],a);
        if(activenodes[b].size()>activenodes[a].size())swap(activenodes[a],activenodes[b]);
        for(int i:activenodes[b])activenodes[a].emplace(i);
    }
    void eraseTill(int x){
        while(!ses.empty() and ses.begin()->first<x){
            activenodes[ses.begin()->second].clear();
            ses.erase(ses.begin());
        }
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<int> s(N+1);
    map<int,vector<int>> villages;
    for(int i=1;i<=N;i++){
        cin>>s[i];
        villages[s[i]].emplace_back(i);
    }
    vector<vector<int>> adj(N+1);
    for(int i=1;i<=M;i++){
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    UFDS dsu(N,s);
    for(auto[pop,vec]:villages){
        dsu.eraseTill(pop);
        for(int&i:vec)dsu.activate(i);
        for(int&i:vec){
            for(int&j:adj[i])if(s[j]<=pop){
                dsu.unite(i,j);
            }
        }
    }
    int root = dsu.findRoot(1);
    vector<bool> ans(N+1);
    for(int i:dsu.activenodes[root])ans[i]=true;
    for(int i=1;i<=N;i++)cout<<(ans[i]?'1':'0');
    cout << '\n';
}

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