oj.uz

Submission #753917

# Submission time Handle Problem Language Result Execution time Memory
753917 2023-06-06T10:10:07 Z Abito Stranded Far From Home (BOI22_island) C++14
20 / 100
 1000 ms 243312 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];
vector<int> adj[N],v;
bool cmp(int x,int y){
    return dis[x]<dis[y];
}
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);
    cin>>n>>m;
    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 (n<=2000 && m<=2000){
        for (int i=1;i<=n;i++) cout<<check(i);
        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 3 ms 5032 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 329 ms 5160 KB Output is correct
5 Correct 275 ms 5148 KB Output is correct
6 Correct 567 ms 5172 KB Output is correct
7 Correct 368 ms 5172 KB Output is correct
8 Correct 261 ms 5152 KB Output is correct
9 Correct 467 ms 5208 KB Output is correct
10 Correct 155 ms 5136 KB Output is correct
11 Correct 152 ms 5076 KB Output is correct
12 Correct 133 ms 5076 KB Output is correct
13 Correct 398 ms 5200 KB Output is correct
14 Correct 185 ms 5136 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 159 ms 26948 KB Output is correct
4 Correct 139 ms 26880 KB Output is correct
5 Correct 187 ms 20380 KB Output is correct
6 Correct 182 ms 20712 KB Output is correct
7 Correct 174 ms 20764 KB Output is correct
8 Correct 191 ms 20816 KB Output is correct
9 Correct 143 ms 22068 KB Output is correct
10 Correct 107 ms 22188 KB Output is correct
11 Correct 107 ms 22184 KB Output is correct
12 Correct 189 ms 20808 KB Output is correct
13 Correct 157 ms 35388 KB Output is correct
14 Correct 166 ms 35356 KB Output is correct
15 Correct 143 ms 35328 KB Output is correct
16 Correct 99 ms 35096 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Incorrect 173 ms 35196 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 4948 KB Output is correct
2 Execution timed out 1086 ms 243312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 329 ms 5160 KB Output is correct
5 Correct 275 ms 5148 KB Output is correct
6 Correct 567 ms 5172 KB Output is correct
7 Correct 368 ms 5172 KB Output is correct
8 Correct 261 ms 5152 KB Output is correct
9 Correct 467 ms 5208 KB Output is correct
10 Correct 155 ms 5136 KB Output is correct
11 Correct 152 ms 5076 KB Output is correct
12 Correct 133 ms 5076 KB Output is correct
13 Correct 398 ms 5200 KB Output is correct
14 Correct 185 ms 5136 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 159 ms 26948 KB Output is correct
18 Correct 139 ms 26880 KB Output is correct
19 Correct 187 ms 20380 KB Output is correct
20 Correct 182 ms 20712 KB Output is correct
21 Correct 174 ms 20764 KB Output is correct
22 Correct 191 ms 20816 KB Output is correct
23 Correct 143 ms 22068 KB Output is correct
24 Correct 107 ms 22188 KB Output is correct
25 Correct 107 ms 22184 KB Output is correct
26 Correct 189 ms 20808 KB Output is correct
27 Correct 157 ms 35388 KB Output is correct
28 Correct 166 ms 35356 KB Output is correct
29 Correct 143 ms 35328 KB Output is correct
30 Correct 99 ms 35096 KB Output is correct
31 Correct 3 ms 5036 KB Output is correct
32 Incorrect 173 ms 35196 KB Output isn't correct
33 Halted 0 ms 0 KB -