oj.uz

Submission #753930

# Submission time Handle Problem Language Result Execution time Memory
753930 2023-06-06T10:43:16 Z Abito Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 287580 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;
    for (int i=1;i<=n;i++) cin>>a[i];
    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;
    }
    if (n<=2000 && m<=2000){
        for (int i=1;i<=n;i++) cout<<check(i);
        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;
    }
    dfs(1,0,0);
    for (int i=2;i<=n;i++) v.pb(i);
    sort(v.begin(),v.end(),cmp);
    //for (int i=1;i<=n;i++) cout<<dp[i]<<endl;
    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;
}

Subtask #1
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 4 ms 6484 KB Output is correct
4 Correct 349 ms 6692 KB Output is correct
5 Correct 263 ms 6612 KB Output is correct
6 Correct 540 ms 6708 KB Output is correct
7 Correct 335 ms 6700 KB Output is correct
8 Correct 249 ms 6696 KB Output is correct
9 Correct 457 ms 6756 KB Output is correct
10 Correct 162 ms 6612 KB Output is correct
11 Correct 141 ms 6672 KB Output is correct
12 Correct 130 ms 6696 KB Output is correct
13 Correct 337 ms 6740 KB Output is correct
14 Correct 170 ms 6696 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 139 ms 28488 KB Output is correct
4 Correct 166 ms 28524 KB Output is correct
5 Correct 167 ms 21940 KB Output is correct
6 Correct 171 ms 22312 KB Output is correct
7 Correct 162 ms 22456 KB Output is correct
8 Correct 186 ms 22412 KB Output is correct
9 Correct 145 ms 23552 KB Output is correct
10 Correct 102 ms 23712 KB Output is correct
11 Correct 130 ms 23664 KB Output is correct
12 Correct 178 ms 22396 KB Output is correct
13 Incorrect 139 ms 48652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Incorrect 302 ms 48596 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 6612 KB Output is correct
2 Execution timed out 1091 ms 287580 KB Time limit exceeded
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 4 ms 6484 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 349 ms 6692 KB Output is correct
5 Correct 263 ms 6612 KB Output is correct
6 Correct 540 ms 6708 KB Output is correct
7 Correct 335 ms 6700 KB Output is correct
8 Correct 249 ms 6696 KB Output is correct
9 Correct 457 ms 6756 KB Output is correct
10 Correct 162 ms 6612 KB Output is correct
11 Correct 141 ms 6672 KB Output is correct
12 Correct 130 ms 6696 KB Output is correct
13 Correct 337 ms 6740 KB Output is correct
14 Correct 170 ms 6696 KB Output is correct
15 Correct 4 ms 6484 KB Output is correct
16 Correct 3 ms 6612 KB Output is correct
17 Correct 139 ms 28488 KB Output is correct
18 Correct 166 ms 28524 KB Output is correct
19 Correct 167 ms 21940 KB Output is correct
20 Correct 171 ms 22312 KB Output is correct
21 Correct 162 ms 22456 KB Output is correct
22 Correct 186 ms 22412 KB Output is correct
23 Correct 145 ms 23552 KB Output is correct
24 Correct 102 ms 23712 KB Output is correct
25 Correct 130 ms 23664 KB Output is correct
26 Correct 178 ms 22396 KB Output is correct
27 Incorrect 139 ms 48652 KB Output isn't correct
28 Halted 0 ms 0 KB -