oj.uz

Submission #641567

# Submission time Handle Problem Language Result Execution time Memory
641567 2022-09-17T03:48:09 Z kebine Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 12960 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
vector<int> g[N];
int a[N], n, m;

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

    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    for(int i = 0; i < n; i++) {
        ll cur = a[i], cnt = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
        q.push({a[i], i});
        vector<bool> vis(n);
        vis[i] = 1;
        while(!q.empty()) {
            auto [val, v] = q.top(); q.pop();
            if(v != i) {
                if(cur < val) {
                    break;
                } else {
                    cur += val;
                }
            }
            cnt++;
            
            for(auto u : g[v]) {
                if(!vis[u]) {
                    vis[u] = 1;
                    q.push({a[u], u});
                }
            }
        }

        cout << (cnt == n ? '1' : '0');
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 152 ms 5076 KB Output is correct
5 Correct 171 ms 5076 KB Output is correct
6 Correct 202 ms 5100 KB Output is correct
7 Correct 158 ms 5112 KB Output is correct
8 Correct 115 ms 5092 KB Output is correct
9 Correct 225 ms 5120 KB Output is correct
10 Correct 65 ms 5120 KB Output is correct
11 Correct 61 ms 5116 KB Output is correct
12 Correct 63 ms 5108 KB Output is correct
13 Correct 118 ms 5112 KB Output is correct
14 Correct 99 ms 5076 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 2 ms 4948 KB Output is correct
3 Execution timed out 1083 ms 12960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1093 ms 11908 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 4948 KB Output is correct
2 Execution timed out 1097 ms 12112 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 152 ms 5076 KB Output is correct
5 Correct 171 ms 5076 KB Output is correct
6 Correct 202 ms 5100 KB Output is correct
7 Correct 158 ms 5112 KB Output is correct
8 Correct 115 ms 5092 KB Output is correct
9 Correct 225 ms 5120 KB Output is correct
10 Correct 65 ms 5120 KB Output is correct
11 Correct 61 ms 5116 KB Output is correct
12 Correct 63 ms 5108 KB Output is correct
13 Correct 118 ms 5112 KB Output is correct
14 Correct 99 ms 5076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1083 ms 12960 KB Time limit exceeded
18 Halted 0 ms 0 KB -