Submission #1205807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205807		lighton	Stranded Far From Home (BOI22_island)	C++20	100 / 100	226 ms	82900 KiB

island

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N,M;
pair<ll,int> S[1000001];
vector<int> G[1000001];
int num[1000001];
vector<int> ch[1000001];
int in[1000001], out[1000001], ord;
ll sum[1000001];
int ans[1000001];

void dfs(int now){
    sum[now] = S[num[now]].fs;
    in[now] = ++ord;
    for(auto i : ch[now]){
        dfs(i);
        sum[now] += sum[i];
    }
    out[now] = ord;
}

struct Seg{
    ll arr[4000001];
    void update(int now, int s, int e, int f, ll x){
        if(s==e){ arr[now] = x; return; }
        int m = s+e>>1;
        if(f<=m) update(now*2,s,m,f,x);
        else update(now*2+1,m+1,e,f,x);
        arr[now] = min(arr[now*2], arr[now*2+1]);
    }
    ll query(int now, int s, int e, int l, int r){
        if(l>r) return inf;
        if(l<=s && e<=r) return arr[now];
        if(l>e || r<s) return inf;
        int m = s+e>>1;
        return min(query(now*2,s,m,l,r) , query(now*2+1,m+1,e,l,r));
    }
} seg;
struct DSU{
    int grp[1000001];
    void init(int n){forf(i,1,n) grp[i] = i;}
    int fi(int x){
        if(grp[x] == x) return x;
        return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x), y = fi(y);
        if(num[x] < num[y]) grp[x] = y;
        else grp[y] = x;
    }
} dsu;

void upd(int u){
    ans[u] = 1;
    for(auto v : G[u]){
        seg.update(1,1,N,in[v],S[num[u]].fs);
    }
}

int main(){
    IO
    cin>>N>>M;
    forf(i,1,N) cin>>S[i].fs, S[i].se = i;
    forf(i,1,M){int u,v; cin>>u>>v; G[u].pb(v), G[v].pb(u);}
    sort(S+1,S+N+1);
    forf(i,1,N) num[S[i].se] = i;

    dsu.init(N);
    forf(i,1,N){
        int u = S[i].se;
        for(auto v : G[u]) if(num[v] < num[u] && dsu.fi(v) != dsu.fi(u)) ch[u].pb(dsu.fi(v)), dsu.un(u,v);
    }

    dfs(S[N].se);
    forf(i,1,N) seg.update(1,1,N,i,inf);
    upd(S[N].se);

    forb(i,N-1,1){
        int u = S[i].se;
        if(sum[u] >= seg.query(1,1,N,in[u], out[u])) upd(u);
    }

    forf(i,1,N) cout<<ans[i];
}

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