oj.uz

Submission #714615

# Submission time Handle Problem Language Result Execution time Memory
714615 2023-03-25T06:39:26 Z TheSahib Stranded Far From Home (BOI22_island) C++14
10 / 100
 343 ms 12260 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);
    }
    if(n > 2000 || m > 2000){
        cout << 1;
        for (int i = 2; i <= n; i++)
        {
            cout << (arr[i] == arr[1]);
        }
        return 0;
    }
    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 2 ms 4948 KB Output is correct
4 Correct 223 ms 5076 KB Output is correct
5 Correct 194 ms 5076 KB Output is correct
6 Correct 343 ms 5068 KB Output is correct
7 Correct 225 ms 5076 KB Output is correct
8 Correct 170 ms 5048 KB Output is correct
9 Correct 299 ms 5116 KB Output is correct
10 Correct 95 ms 5076 KB Output is correct
11 Correct 93 ms 5076 KB Output is correct
12 Correct 111 ms 5076 KB Output is correct
13 Correct 170 ms 5076 KB Output is correct
14 Correct 105 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 Incorrect 276 ms 12260 KB Output isn't correct
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 Incorrect 238 ms 12164 KB Output isn't correct
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 Incorrect 266 ms 12136 KB Output isn't correct
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 2 ms 4948 KB Output is correct
4 Correct 223 ms 5076 KB Output is correct
5 Correct 194 ms 5076 KB Output is correct
6 Correct 343 ms 5068 KB Output is correct
7 Correct 225 ms 5076 KB Output is correct
8 Correct 170 ms 5048 KB Output is correct
9 Correct 299 ms 5116 KB Output is correct
10 Correct 95 ms 5076 KB Output is correct
11 Correct 93 ms 5076 KB Output is correct
12 Correct 111 ms 5076 KB Output is correct
13 Correct 170 ms 5076 KB Output is correct
14 Correct 105 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 Incorrect 276 ms 12260 KB Output isn't correct
18 Halted 0 ms 0 KB -