oj.uz

Submission #711223

# Submission time Handle Problem Language Result Execution time Memory
711223 2023-03-16T10:28:20 Z safaricola Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 15940 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i = 1; i <= n; i++)
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define debug(x) cout<<#x<<' '<<x<<endl;

vector<int> adj[200010];
int n,m,a[200010];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    rep(i,n)cin>>a[i];
    rep(i,m){
        int A,B;cin>>A>>B;
        adj[A].pb(B);
        adj[B].pb(A);
    }
    rep(i,n){
        bool vis[200010]={};
        int cur=a[i];
        priority_queue<ii,vector<ii>, greater<ii> > pq;
        pq.push({0,i});
        vis[i]=1;
        while(!pq.empty()&&pq.top().f<=cur){
            cur+=pq.top().f;
            int v=pq.top().s;
           // cout<<v<<' '<<cur<<endl;
            pq.pop();
            for(int u: adj[v]){
                if(!vis[u]){
                    vis[u]=1;
                    pq.push({a[u],u});
                }
            }
        }
        if(pq.empty())cout<<1;else cout<<0;
    }
    
}
/*
4 4
2 2 4 3  
1 2
1 3
2 3
3 4

4 3 
4 2 2 1 
1 2
3 2
4 1
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 160 ms 5328 KB Output is correct
5 Correct 154 ms 5332 KB Output is correct
6 Correct 212 ms 5360 KB Output is correct
7 Correct 161 ms 5332 KB Output is correct
8 Correct 116 ms 5332 KB Output is correct
9 Correct 220 ms 5364 KB Output is correct
10 Correct 73 ms 5332 KB Output is correct
11 Correct 68 ms 5328 KB Output is correct
12 Correct 70 ms 5224 KB Output is correct
13 Correct 122 ms 5204 KB Output is correct
14 Correct 97 ms 5332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Execution timed out 1101 ms 15940 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Execution timed out 1010 ms 13596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Execution timed out 1057 ms 14928 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 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 160 ms 5328 KB Output is correct
5 Correct 154 ms 5332 KB Output is correct
6 Correct 212 ms 5360 KB Output is correct
7 Correct 161 ms 5332 KB Output is correct
8 Correct 116 ms 5332 KB Output is correct
9 Correct 220 ms 5364 KB Output is correct
10 Correct 73 ms 5332 KB Output is correct
11 Correct 68 ms 5328 KB Output is correct
12 Correct 70 ms 5224 KB Output is correct
13 Correct 122 ms 5204 KB Output is correct
14 Correct 97 ms 5332 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5212 KB Output is correct
17 Execution timed out 1101 ms 15940 KB Time limit exceeded
18 Halted 0 ms 0 KB -