oj.uz

Submission #753933

# Submission time Handle Problem Language Result Execution time Memory
753933 2023-06-06T10:48:28 Z Abito Stranded Far From Home (BOI22_island) C++14
20 / 100
 527 ms 48452 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<=5;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 3 ms 6484 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 349 ms 6688 KB Output is correct
5 Correct 276 ms 6696 KB Output is correct
6 Correct 527 ms 6704 KB Output is correct
7 Correct 351 ms 6712 KB Output is correct
8 Correct 282 ms 6700 KB Output is correct
9 Correct 458 ms 6752 KB Output is correct
10 Correct 156 ms 6680 KB Output is correct
11 Correct 158 ms 6672 KB Output is correct
12 Correct 137 ms 6696 KB Output is correct
13 Correct 353 ms 6740 KB Output is correct
14 Correct 180 ms 6612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 163 ms 28528 KB Output is correct
4 Correct 147 ms 28484 KB Output is correct
5 Correct 159 ms 21884 KB Output is correct
6 Correct 182 ms 22376 KB Output is correct
7 Correct 167 ms 22476 KB Output is correct
8 Correct 177 ms 22380 KB Output is correct
9 Correct 157 ms 23584 KB Output is correct
10 Correct 100 ms 23712 KB Output is correct
11 Correct 101 ms 23672 KB Output is correct
12 Correct 172 ms 22368 KB Output is correct
13 Correct 151 ms 36952 KB Output is correct
14 Correct 136 ms 36892 KB Output is correct
15 Correct 157 ms 36868 KB Output is correct
16 Correct 102 ms 36640 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 349 ms 6688 KB Output is correct
5 Correct 276 ms 6696 KB Output is correct
6 Correct 527 ms 6704 KB Output is correct
7 Correct 351 ms 6712 KB Output is correct
8 Correct 282 ms 6700 KB Output is correct
9 Correct 458 ms 6752 KB Output is correct
10 Correct 156 ms 6680 KB Output is correct
11 Correct 158 ms 6672 KB Output is correct
12 Correct 137 ms 6696 KB Output is correct
13 Correct 353 ms 6740 KB Output is correct
14 Correct 180 ms 6612 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 4 ms 6484 KB Output is correct
17 Correct 163 ms 28528 KB Output is correct
18 Correct 147 ms 28484 KB Output is correct
19 Correct 159 ms 21884 KB Output is correct
20 Correct 182 ms 22376 KB Output is correct
21 Correct 167 ms 22476 KB Output is correct
22 Correct 177 ms 22380 KB Output is correct
23 Correct 157 ms 23584 KB Output is correct
24 Correct 100 ms 23712 KB Output is correct
25 Correct 101 ms 23672 KB Output is correct
26 Correct 172 ms 22368 KB Output is correct
27 Correct 151 ms 36952 KB Output is correct
28 Correct 136 ms 36892 KB Output is correct
29 Correct 157 ms 36868 KB Output is correct
30 Correct 102 ms 36640 KB Output is correct
31 Correct 4 ms 6588 KB Output is correct
32 Incorrect 300 ms 48452 KB Output isn't correct
33 Halted 0 ms 0 KB -