제출 #1121954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121954		adilet_321	Stranded Far From Home (BOI22_island)	C++17	25 / 100	855 ms	21092 KiB

island

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

vector<int>g[222001];
int u[222001];
int c[222001];
int mx=-1;


signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    int a[n+3];
    int ans[n+3];
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx=max(mx,a[i]);
        ans[i]=0;
    }
    for(int i=1;i<=m;i++){
        int q,w;
        cin>>q>>w;
        g[q].push_back(w);
        g[w].push_back(q);
    }
    if(n<=2000 && m<=2000){
        for(int iii=1;iii<=n;iii++){
            int p=a[iii];
            for(int i=1;i<=n;i++){
                u[i]=0;
                c[i]=i;
            }
            for(auto it : g[iii]){
                u[it]=1;
            }
            u[iii]=1;
            int k=1;
            set<pair<int,int>>s;
            for(auto it : g[iii]){
                s.insert({a[it],it});
            }
            while(s.size()!=0){
                pair<int,int>nn=*s.begin();
                if(nn.first>p){
                    break;
                }
                else{
                    p+=nn.first;
                    c[nn.second]=iii;
                    s.erase(s.begin());
                    k++;
                    for(auto it: g[nn.second]){
                        if(c[it]!=iii){
                            s.insert({a[it],it});
                        }
                    }
                }
            }
            if(k==n){
                ans[iii]=1;
            }
        }
    }
    else {
        int pp[n+3];
        pp[0]=0;
        for(int i=1;i<=n;i++){
            pp[i]=pp[i-1]+a[i];
        }
        for(int i=1;i<=n;i++){
            //cout<<i<<"\n\n";
            int l=i,r=i;
            int p=a[i];
            for(int j=1;j<=200;j++){
                if(p>=mx){
                    l=1;
                    r=n;
                    break;
                }
                //int lq=l,rq=r;
                if(r<n){
                    int l1=r+1,r1=n;
                    while(r1-l1>1){
                        int m=(l1+r1)>>1;
                        if(pp[m]-pp[r]<=p){
                            p+=pp[m]-pp[r];
                            r=m;
                            l1=m+1;
                        }
                        else{
                            r1=m;
                        }
                    }
                    if(pp[r1]-pp[r]<=p){
                        p+=pp[r1]-pp[r];
                        r=r1;
                    }
                    else if(pp[l1]-pp[r]<=p){
                        p+=pp[l1]-pp[r];
                        r=l1;
                    }
                }
                if(l>1){
                    int l1=1,r1=l-1;
                    while(r1-l1>1){
                        int m=(l1+r1)>>1;
                        if(pp[l-1]-pp[m-1]<=p){
                            p+=pp[l-1]-pp[m-1];
                            l=m;
                            r1=m-1;
                        }
                        else{
                            l1=m;
                        }
                    }
                    //cout<<pp[l-1]<<" "<<pp[l1-1]<<" "<<pp[r1-1]<<"\n";
                    if(pp[l-1]-pp[l1-1]<=p){
                        p+=pp[l-1]-pp[l1-1];
                        l=l1;
                    }
                    else if(pp[l-1]-pp[r1-1]<=p){
                        p+=pp[l-1]-pp[r1-1];
                        l=r1;
                    }
                }
            }
            if(l==1 && r==n){
                ans[i]=1;
            }
            else{
                ans[i]=0;
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        cout<<ans[i];
    }
}

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