oj.uz

Submission #753935

# Submission time Handle Problem Language Result Execution time Memory
753935 2023-06-06T10:49:48 Z Abito Stranded Far From Home (BOI22_island) C++14
20 / 100
 543 ms 48396 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<=20;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 5 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 330 ms 6692 KB Output is correct
5 Correct 269 ms 6680 KB Output is correct
6 Correct 543 ms 6704 KB Output is correct
7 Correct 366 ms 6612 KB Output is correct
8 Correct 260 ms 6692 KB Output is correct
9 Correct 447 ms 6748 KB Output is correct
10 Correct 149 ms 6672 KB Output is correct
11 Correct 143 ms 6672 KB Output is correct
12 Correct 138 ms 6708 KB Output is correct
13 Correct 360 ms 6740 KB Output is correct
14 Correct 190 ms 6680 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 3 ms 6484 KB Output is correct
3 Correct 148 ms 28508 KB Output is correct
4 Correct 146 ms 28448 KB Output is correct
5 Correct 204 ms 21892 KB Output is correct
6 Correct 172 ms 22324 KB Output is correct
7 Correct 210 ms 22384 KB Output is correct
8 Correct 192 ms 22436 KB Output is correct
9 Correct 153 ms 23620 KB Output is correct
10 Correct 107 ms 23772 KB Output is correct
11 Correct 101 ms 23660 KB Output is correct
12 Correct 159 ms 22352 KB Output is correct
13 Correct 132 ms 37012 KB Output is correct
14 Correct 131 ms 36920 KB Output is correct
15 Correct 134 ms 36892 KB Output is correct
16 Correct 96 ms 36656 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 330 ms 48396 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 121 ms 15412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6484 KB Output is correct
2 Correct 5 ms 6484 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 330 ms 6692 KB Output is correct
5 Correct 269 ms 6680 KB Output is correct
6 Correct 543 ms 6704 KB Output is correct
7 Correct 366 ms 6612 KB Output is correct
8 Correct 260 ms 6692 KB Output is correct
9 Correct 447 ms 6748 KB Output is correct
10 Correct 149 ms 6672 KB Output is correct
11 Correct 143 ms 6672 KB Output is correct
12 Correct 138 ms 6708 KB Output is correct
13 Correct 360 ms 6740 KB Output is correct
14 Correct 190 ms 6680 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 3 ms 6484 KB Output is correct
17 Correct 148 ms 28508 KB Output is correct
18 Correct 146 ms 28448 KB Output is correct
19 Correct 204 ms 21892 KB Output is correct
20 Correct 172 ms 22324 KB Output is correct
21 Correct 210 ms 22384 KB Output is correct
22 Correct 192 ms 22436 KB Output is correct
23 Correct 153 ms 23620 KB Output is correct
24 Correct 107 ms 23772 KB Output is correct
25 Correct 101 ms 23660 KB Output is correct
26 Correct 159 ms 22352 KB Output is correct
27 Correct 132 ms 37012 KB Output is correct
28 Correct 131 ms 36920 KB Output is correct
29 Correct 134 ms 36892 KB Output is correct
30 Correct 96 ms 36656 KB Output is correct
31 Correct 3 ms 6484 KB Output is correct
32 Incorrect 330 ms 48396 KB Output isn't correct
33 Halted 0 ms 0 KB -