Submission #624116

#	Time	Username	Problem	Language	Result	Execution time	Memory
624116		Andyvanh1	Stranded Far From Home (BOI22_island)	C++14	100 / 100	311 ms	58036 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define vt vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define FORR1(x) for(int i = 0; i < (x); i++)
#define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
#define f first
#define s second
#define MOD 998244353
#define INF INT_MAX

typedef vt<int> vi;
typedef vt<long long> vl;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;

struct Segtree{
    vl arr;
    vl lz1;
    vl lz2;
    int sz = 1;


    void init(int n, vl cop) {
        while(sz<n)sz*=2;
        arr.resize(2*sz);
        lz1.resize(2*sz);
        lz2.resize(2*sz);
        FORR1(n){
            arr[sz+i] = cop[i];
        }
        FORR1(sz-n){
            arr[sz+i+n] = 0;
        }
        for(int i = sz-1; i>0; i--){
            arr[i] = arr[2*i]+arr[2*i+1];
        }
        FORR1(2*sz){
            lz1[i] = lz2[i] = 0;
        }
    }

    void pushlazy(int x, int lth){
        if(lth==1){
            arr[x] += lz1[x];
            lz1[x] = 0;
            lz2[x] = 0;
            return;
        }
        arr[x] += lz1[x]*lth + (((ll)lth*(lth-1))>>1)*lz2[x];
        lz1[2*x] +=lz1[x];
        lz2[2*x] += lz2[x];
        lz1[2*x+1] += lz1[x]+(lth>>1)*lz2[x];
        lz2[2*x+1] += lz2[x];
        lz1[x] = lz2[x] = 0;
    }


    void add(int index, int val){
        int cur = index+sz;
        while(cur!=0){
            arr[cur]+=val;
            cur>>=1;
        }
    }

    ll get(int l, int r, int x, int lx, int rx){
        if(lx>r||l>rx){
            return 0;
        }else if(l<=lx && r>=rx){

            pushlazy(x,rx-lx+1);
            return arr[x];
        }else{
            pushlazy(x,rx-lx+1);
            int mid = (lx+rx)>>1;
            return get(l,r,2*x,lx,mid)+get(l,r,2*x+1,mid+1,rx);
        }
    }

    ll get(int l, int r){
        return get(l,r,1,0,sz-1);
    }

    void set1(int l, int r, int x, int lx, int rx){
        pushlazy(x,rx-lx+1);
        if(l>rx||r<lx){
            return;
        }else if(l<=lx&&r>=rx){
            lz1[x] = 1+lx-l;
            lz2[x] = 1;
            pushlazy(x,rx-lx+1);
        }else{
            int mid = (lx+rx)>>1;
            set1(l,r,2*x,lx,mid);
            set1(l,r,2*x+1,mid+1,rx);
            arr[x] = arr[2*x]+arr[2*x+1];
        }
    }

    void set1(int l, int r){
        set1(l,r,1,0,sz-1);
    }




};

int pp[200005];
ll sums[200005];
int vals[200005];
vi up[200005];
vi dn[200005];
bool ans[200005];
set<pli> st[200005];

int find(int x){
    return (x==pp[x] ? x : pp[x] = find(pp[x]));
}

void join(int a, int b){
    int u = find(a), v = find(b);
    if(u==v)return;
    if(st[u].size()<st[v].size())swap(u,v);
    for(auto& e: st[v])st[u].insert(e);
    sums[u]+=sums[v];
    pp[v] = u;
}

int go[200005];



void solve() {
    int n, m;
    cin>>n>>m;
    FORR1(n)cin>>vals[i];
    FORR1(m){
        int u, v;
        cin>>u>>v;u--;v--;
        if(make_pair(vals[u],u)>make_pair(vals[v],v)){
            up[v].pb(u);
            dn[u].pb(v);
        }else{
            up[u].pb(v);
            dn[v].pb(u);
        }
    }
    vt<pli> arr(n);
    FORR1(n)arr[i] = {vals[i],i};
    sort(all(arr));
    FORR1(n){
        pp[i] = i;
        sums[i] = vals[i];
        go[i] = -1;
    }
    FORR1(n){
        for(auto& e: up[i]){
            st[i].insert({vals[e],e});
        }
    }

    FORR1(n){
        int x = arr[i].s;
        for(auto& e: dn[x]){
            join(x,e);
        }
        int u = find(x);
        if(dn[x].size()!=0)st[u].erase(st[u].find(arr[i]));
        if(!st[u].empty()){
            auto it = *st[u].begin();
            if(sums[u]>=it.f){
                go[x] = it.s;
            }
        }
    }
    ans[arr[n-1].s] = 1;
    for(int i = n-2; i>=0; i--){
        int x = arr[i].s;
        if(go[x]!=-1&&ans[go[x]]){
            ans[x] = 1;
        }else{
            ans[x] = 0;
        }
    }
    FORR1(n)cout<<ans[i];
    cout<<'\n';









}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

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