oj.uz

Submission #714609

# Submission time Handle Problem Language Result Execution time Memory
714609 2023-03-25T06:33:44 Z TheSahib Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 13640 KB 
#include <bits/stdc++.h>


#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 2e5 + 5;


int n, m;
int arr[MAX];
vector<int> g[MAX];


bool visited[MAX];
bool bfs(int start){
    fill(visited, visited + n + 1, 0);
    
    ll cnt = 0;
    
    set<pii> q;
    q.insert({arr[start], start});
    while(!q.empty()){
        int node = q.begin()->second;
        int c = q.begin()->first;
        q.erase(q.begin());
        visited[node] = true;
        if(cnt >= c || node == start){
            cnt += c;
            for(int to:g[node]){
                if(visited[to]) continue;
                q.insert({arr[to], to});
            }
        }
        else{
            return false;
        }
    }
    return true;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << bfs(i);
    }
}

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 235 ms 5076 KB Output is correct
5 Correct 201 ms 5076 KB Output is correct
6 Correct 341 ms 5056 KB Output is correct
7 Correct 213 ms 5056 KB Output is correct
8 Correct 169 ms 5052 KB Output is correct
9 Correct 300 ms 5100 KB Output is correct
10 Correct 123 ms 5076 KB Output is correct
11 Correct 98 ms 5076 KB Output is correct
12 Correct 124 ms 4948 KB Output is correct
13 Correct 183 ms 5076 KB Output is correct
14 Correct 113 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 3 ms 4948 KB Output is correct
3 Execution timed out 1091 ms 13640 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 1079 ms 12104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1075 ms 12568 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 235 ms 5076 KB Output is correct
5 Correct 201 ms 5076 KB Output is correct
6 Correct 341 ms 5056 KB Output is correct
7 Correct 213 ms 5056 KB Output is correct
8 Correct 169 ms 5052 KB Output is correct
9 Correct 300 ms 5100 KB Output is correct
10 Correct 123 ms 5076 KB Output is correct
11 Correct 98 ms 5076 KB Output is correct
12 Correct 124 ms 4948 KB Output is correct
13 Correct 183 ms 5076 KB Output is correct
14 Correct 113 ms 5076 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 1091 ms 13640 KB Time limit exceeded
18 Halted 0 ms 0 KB -