oj.uz

Submission #640260

# Submission time Handle Problem Language Result Execution time Memory
640260 2022-09-14T04:53:48 Z kebine Stranded Far From Home (BOI22_island) C++17
10 / 100
 188 ms 1748 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>

using namespace std;

const int N = 20002;
vector<int>adj[N];
bool vis[N];
ll s[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> s[i];

    while(m--){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof(vis));
        priority_queue<pll, vector<pll>, greater<pll>>q; q.emplace(0, i);
        vis[i] = true;
        int cnt = 0;
        ll cur = s[i];

        while(!q.empty()){
            auto [v, u] = q.top(); q.pop();
            if(cur < v) break;
            cnt++;
            cur += v;

            for(auto &v: adj[u]){
                if(!vis[v]){
                    vis[v] = true;
                    q.emplace(s[v], v);
                }
            }
        }

        if(cnt == n) cout << 1;
        else cout << 0;
    }

    cout << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 157 ms 852 KB Output is correct
5 Correct 131 ms 920 KB Output is correct
6 Correct 188 ms 972 KB Output is correct
7 Correct 148 ms 920 KB Output is correct
8 Correct 98 ms 888 KB Output is correct
9 Correct 187 ms 936 KB Output is correct
10 Correct 44 ms 916 KB Output is correct
11 Correct 46 ms 932 KB Output is correct
12 Correct 53 ms 908 KB Output is correct
13 Correct 83 ms 896 KB Output is correct
14 Correct 96 ms 904 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Runtime error 9 ms 1748 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Runtime error 10 ms 1736 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Runtime error 9 ms 1748 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 157 ms 852 KB Output is correct
5 Correct 131 ms 920 KB Output is correct
6 Correct 188 ms 972 KB Output is correct
7 Correct 148 ms 920 KB Output is correct
8 Correct 98 ms 888 KB Output is correct
9 Correct 187 ms 936 KB Output is correct
10 Correct 44 ms 916 KB Output is correct
11 Correct 46 ms 932 KB Output is correct
12 Correct 53 ms 908 KB Output is correct
13 Correct 83 ms 896 KB Output is correct
14 Correct 96 ms 904 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Runtime error 9 ms 1748 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -