oj.uz

Submission #753934

# Submission time Handle Problem Language Result Execution time Memory
753934 2023-06-06T10:49:16 Z Abito Stranded Far From Home (BOI22_island) C++14
20 / 100
 529 ms 48460 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
typedef unsigned long long ull;
using namespace std;
const int N=2e5+5;
int n,m,a[N],dis[N],par[N],dp[N],st[25][N],p[N],lg[N],L[N],R[N];
vector<int> adj[N],v;
bool cmp(int x,int y){
    return dis[x]<dis[y];
}
bool cmpp(int x,int y){
    return a[x]>a[y];
}
void build(){
    for (int i=0;i<=n+1;i++) st[0][i]=a[i];
    for (int i=1;i<25;i++){
        for (int j=0;j+(1<<i)<=n+2;j++){
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        }
    }return;
}
int query(int l,int r){
    if (l>r) swap(l,r);
    int i=lg[r-l+1];
    return max(st[i][l],st[i][r-(1<<i)+1]);
}
bool check(int source){
    priority_queue<pair<int,int>> pq;
    bool vis[n+5];
    memset(vis,0,sizeof(vis));
    int c=a[source];
    for (auto u:adj[source]) pq.push({-a[u],u});
    vis[source]=true;
    while (!pq.empty()){
        pair<int,int> x=pq.top();
        pq.pop();
        x.F*=-1;
        if (vis[x.S]) continue;
        if (x.F>c) break;
        vis[x.S]=true;
        c+=x.F;
        for (auto u:adj[x.S]) pq.push({-a[u],u});
    }
    bool ok=true;
    for (int i=1;i<=n;i++){
        if (vis[i]) continue;
        ok=false;
        break;
    }return ok;
}
void dfs(int node,int d,int p){
    dis[node]=d;
    dp[node]=a[node];
    par[node]=p;
    for (auto u:adj[node]){
        if (u==p) continue;
        dfs(u,d+1,node);
        dp[node]+=dp[u];
    }return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    for (int i=2;i<N;i++) lg[i]=lg[i/2]+1;
    cin>>n>>m;
    bool sub3=true,sub2=true;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++){
        if (a[i]>=a[i+1]) continue;
        sub2=false;
    }
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        if (abs(x-y)!=1) sub3=false;
    }
    for (int i=2;i<=n;i++){
        int x=0;
        for (auto u:adj[i]) x+=bool(u<i);
        if (x!=1) sub2=false;
    }
    if (n<=2000 && m<=2000){
        for (int i=1;i<=n;i++) cout<<check(i);
        return 0;
    }
    if (sub2){
        dfs(1,0,0);
        for (int i=2;i<=n;i++) v.pb(i);
        sort(v.begin(),v.end(),cmp);
        for (auto node:v){
            if (dp[node]<a[par[node]]) continue;
            dp[node]=dp[par[node]];
        }
        for (int i=1;i<=n;i++) cout<<bool(dp[i]==dp[1]);
        return 0;
    }
    if (sub3){
        a[0]=LLONG_MAX,a[n+1]=a[0];
        for (int i=1;i<=n;i++) p[i]=p[i-1]+a[i];
        build();
        vector<int> v;
        for (int i=1;i<=n;i++) v.pb(i);
        sort(v.begin(),v.end(),cmpp);
        for (auto u:v){
            int l=0,r=u,mid;
            while (l<=r){
                //cout<<l<<' '<<r<<' ';
                mid=(l+r)/2;
                int x=query(mid,u);
                //cout<<x<<endl;
                if (x<=a[u]){
                    L[u]=mid;
                    r=mid-1;
                }else l=mid+1;
            }
            l=u,r=n+1;
            while (l<=r){
                mid=(l+r)/2;
                int x=query(mid,u);
                if (x<=a[u]){
                    R[u]=mid;
                    l=mid+1;
                }else r=mid-1;
            }dp[u]=p[R[u]]-p[L[u]-1];
            int x=R[u]+1,y=L[u]+1;
            if (a[x]>a[y]) swap(x,y);
            for (int k=1;k<=10;k++){
                if (dp[u]>=a[x]){
                    L[u]=min(L[u],L[x]);
                    dp[u]=p[R[u]]-p[L[u]-1];
                }
                if (dp[u]>=a[y]){
                    R[u]=max(R[u],R[y]);
                    dp[u]=p[R[u]]-p[L[u]-1];
                }
            }
        }
        for (int i=1;i<=n;i++) cout<<bool(dp[i]==p[n]);
        return 0;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 313 ms 6692 KB Output is correct
5 Correct 277 ms 6612 KB Output is correct
6 Correct 529 ms 6704 KB Output is correct
7 Correct 336 ms 6704 KB Output is correct
8 Correct 244 ms 6696 KB Output is correct
9 Correct 461 ms 6752 KB Output is correct
10 Correct 148 ms 6672 KB Output is correct
11 Correct 147 ms 6668 KB Output is correct
12 Correct 133 ms 6704 KB Output is correct
13 Correct 348 ms 6740 KB Output is correct
14 Correct 190 ms 6684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 158 ms 28564 KB Output is correct
4 Correct 152 ms 28572 KB Output is correct
5 Correct 182 ms 21952 KB Output is correct
6 Correct 169 ms 22344 KB Output is correct
7 Correct 169 ms 22380 KB Output is correct
8 Correct 209 ms 22396 KB Output is correct
9 Correct 134 ms 23592 KB Output is correct
10 Correct 100 ms 23736 KB Output is correct
11 Correct 110 ms 23756 KB Output is correct
12 Correct 163 ms 22348 KB Output is correct
13 Correct 140 ms 36896 KB Output is correct
14 Correct 152 ms 36928 KB Output is correct
15 Correct 174 ms 36856 KB Output is correct
16 Correct 95 ms 36596 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Incorrect 331 ms 48460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Incorrect 103 ms 15396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 313 ms 6692 KB Output is correct
5 Correct 277 ms 6612 KB Output is correct
6 Correct 529 ms 6704 KB Output is correct
7 Correct 336 ms 6704 KB Output is correct
8 Correct 244 ms 6696 KB Output is correct
9 Correct 461 ms 6752 KB Output is correct
10 Correct 148 ms 6672 KB Output is correct
11 Correct 147 ms 6668 KB Output is correct
12 Correct 133 ms 6704 KB Output is correct
13 Correct 348 ms 6740 KB Output is correct
14 Correct 190 ms 6684 KB Output is correct
15 Correct 5 ms 6484 KB Output is correct
16 Correct 4 ms 6484 KB Output is correct
17 Correct 158 ms 28564 KB Output is correct
18 Correct 152 ms 28572 KB Output is correct
19 Correct 182 ms 21952 KB Output is correct
20 Correct 169 ms 22344 KB Output is correct
21 Correct 169 ms 22380 KB Output is correct
22 Correct 209 ms 22396 KB Output is correct
23 Correct 134 ms 23592 KB Output is correct
24 Correct 100 ms 23736 KB Output is correct
25 Correct 110 ms 23756 KB Output is correct
26 Correct 163 ms 22348 KB Output is correct
27 Correct 140 ms 36896 KB Output is correct
28 Correct 152 ms 36928 KB Output is correct
29 Correct 174 ms 36856 KB Output is correct
30 Correct 95 ms 36596 KB Output is correct
31 Correct 3 ms 6484 KB Output is correct
32 Incorrect 331 ms 48460 KB Output isn't correct
33 Halted 0 ms 0 KB -