Submission #805536

#	Time	Username	Problem	Language	Result	Execution time	Memory
805536		winter0101	Stranded Far From Home (BOI22_island)	C++14	100 / 100	389 ms	78552 KiB

island

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=2e5+9;
int lab[maxn*2];
vector<int>a[maxn*2];
int findset(int u){
if (lab[u]==u)return u;
return lab[u]=findset(lab[u]);
}
int nnode=0;
int n,m;
int mx[maxn*2];
void unite(int u,int v,int w){
u=findset(u),v=findset(v);
if (u==v)return;
nnode++;
lab[nnode]=nnode;
a[nnode].pb(u);
a[nnode].pb(v);
mx[nnode]=w;
lab[u]=nnode;
lab[v]=nnode;
}
int b[maxn];
int d[maxn];
struct edg{
    int u,v;
    bool operator <(const edg &p)const {
    return max(b[u],b[v])<max(b[p.u],b[p.v]);
    }
}c[maxn];
long long sub[maxn*2];
int st[maxn*2][21];
void dfs(int u){
for (auto v:a[u]){
    st[v][0]=u;
    for1(j,1,20){
    st[v][j]=st[st[v][j-1]][j-1];
    }
    dfs(v);
    sub[u]+=sub[v];
}
}
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    cin>>n>>m;
    for1(i,1,n){
    cin>>b[i];
    lab[i]=i;
    d[i]=b[i];
    mx[i]=b[i];
    sub[i]+=b[i];
    }
    sort(d+1,d+1+n);
    for1(i,1,m){
    cin>>c[i].u>>c[i].v;
    }
    sort(c+1,c+1+m);
    nnode=n;
    for1(i,1,m){
    unite(c[i].u,c[i].v,max(b[c[i].u],b[c[i].v]));
    }
    dfs(nnode);
    for1(i,1,n){
    long long nn=b[i];
    bool fl=false;
    while (true){
    //cerr<<nn<<'\n';
    int id=upper_bound(d+1,d+1+n,nn)-d;
    if (id==1+n){
        fl=true;
        break;
    }
    int kaka=i;
    for2(j,20,0){
    if (st[kaka][j]==0)continue;
    if (mx[st[kaka][j]]<=nn){
        kaka=st[kaka][j];
    }
    }
    //cout<<sub[kaka]<<'\n';
    long long newsum=sub[kaka];
    int id2=upper_bound(d+1,d+1+n,newsum)-d;
    if (id==id2){
        break;
    }
    nn=newsum;
    }
    cout<<fl;
    }
}

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