oj.uz

Submission #714613

# Submission time Handle Problem Language Result Execution time Memory
714613 2023-03-25T06:38:26 Z TheSahib Stranded Far From Home (BOI22_island) C++14
10 / 100
 337 ms 12244 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 = 1; 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 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 219 ms 5060 KB Output is correct
5 Correct 194 ms 5076 KB Output is correct
6 Correct 337 ms 5076 KB Output is correct
7 Correct 217 ms 5056 KB Output is correct
8 Correct 167 ms 5060 KB Output is correct
9 Correct 293 ms 5104 KB Output is correct
10 Correct 98 ms 5056 KB Output is correct
11 Correct 94 ms 5060 KB Output is correct
12 Correct 114 ms 5056 KB Output is correct
13 Correct 174 ms 5076 KB Output is correct
14 Correct 110 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 Incorrect 247 ms 12244 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 242 ms 12128 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 249 ms 12184 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 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 219 ms 5060 KB Output is correct
5 Correct 194 ms 5076 KB Output is correct
6 Correct 337 ms 5076 KB Output is correct
7 Correct 217 ms 5056 KB Output is correct
8 Correct 167 ms 5060 KB Output is correct
9 Correct 293 ms 5104 KB Output is correct
10 Correct 98 ms 5056 KB Output is correct
11 Correct 94 ms 5060 KB Output is correct
12 Correct 114 ms 5056 KB Output is correct
13 Correct 174 ms 5076 KB Output is correct
14 Correct 110 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 Incorrect 247 ms 12244 KB Output isn't correct
18 Halted 0 ms 0 KB -