oj.uz

Submission #753907

# Submission time Handle Problem Language Result Execution time Memory
753907 2023-06-06T09:45:50 Z Abito Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 18888 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];
vector<int> adj[N];
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;
}
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);
    }
    for (int i=1;i<=n;i++) cout<<check(i);
    return 0;
}

Subtask #1
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 3 ms 4948 KB Output is correct
4 Correct 315 ms 5144 KB Output is correct
5 Correct 282 ms 5144 KB Output is correct
6 Correct 512 ms 5156 KB Output is correct
7 Correct 339 ms 5168 KB Output is correct
8 Correct 313 ms 5140 KB Output is correct
9 Correct 439 ms 5196 KB Output is correct
10 Correct 149 ms 5076 KB Output is correct
11 Correct 144 ms 5128 KB Output is correct
12 Correct 134 ms 5148 KB Output is correct
13 Correct 390 ms 5076 KB Output is correct
14 Correct 177 ms 5196 KB Output is correct

Subtask #2
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 Execution timed out 1041 ms 18888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1044 ms 13520 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 5032 KB Output is correct
2 Execution timed out 1055 ms 15136 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 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 315 ms 5144 KB Output is correct
5 Correct 282 ms 5144 KB Output is correct
6 Correct 512 ms 5156 KB Output is correct
7 Correct 339 ms 5168 KB Output is correct
8 Correct 313 ms 5140 KB Output is correct
9 Correct 439 ms 5196 KB Output is correct
10 Correct 149 ms 5076 KB Output is correct
11 Correct 144 ms 5128 KB Output is correct
12 Correct 134 ms 5148 KB Output is correct
13 Correct 390 ms 5076 KB Output is correct
14 Correct 177 ms 5196 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 1041 ms 18888 KB Time limit exceeded
18 Halted 0 ms 0 KB -