Submission #1187020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187020		DanielPr8	Stranded Far From Home (BOI22_island)	C++20	100 / 100	216 ms	45224 KiB

island

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

vvl g, pos;
vll pr, sz, am, mx;

ll get_pr(ll a){
    if(a==pr[a])return a;
    else return pr[a] = get_pr(pr[a]);
}
void ad(vll& a, vll& b){
    if(a.size()>b.size()){
        for(ll i:b)a.pb(i);
    }
    else{
        for(ll i:a)b.pb(i);
        swap(a,b);
    }
}
void unite(ll a, ll b){
    a=get_pr(a);
    b=get_pr(b);
    if(a==b)return;
    if(sz[a]<sz[b])swap(a,b);
    if(am[a]<mx[b])pos[a].clear();
    if(am[b]<mx[a])pos[b].clear();
    ad(pos[a], pos[b]);
    pr[b]=a;
    sz[a]+=sz[b];
    am[a]+=am[b];
    mx[a] = max(mx[a], mx[b]);
}

int main(){
    ll n, m, a, b;
    cin >> n >> m;
    g = pos = vvl(n);
    mx=pr=sz=am=vll(n);
    vll ih(n);
    vpl ord(n);
    for(ll i = 0; i < n; ++i){
        cin >> ih[i];
        pos[i]={i};
        sz[i]=1;
        pr[i]=i;
        am[i]=ih[i];
        mx[i]=ih[i];
        ord[i] = {ih[i], i};
    }
    for(ll i = 0; i < m; ++i){
        cin >> a >> b;a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    sort(all(ord));
    for(auto [c,d]:ord){
        for(ll i:g[d]){
            if(ih[i]<=ih[d]){
                unite(i, d);
            }
        }
    }
    vll ans(n);
    for(ll i:pos[get_pr(0)])ans[i]=1;
    for(ll i:ans)cout << i;


}

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