oj.uz

Submission #714667

# Submission time Handle Problem Language Result Execution time Memory
714667 2023-03-25T07:35:20 Z TheSahib Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 195056 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 subTree[MAX];
bool possible[MAX];
int dfs1(int node, int p){
    int ans = arr[node];
    for(int to:g[node]){
        if(to == p) continue;
        ans += dfs1(to, node);
    }
    subTree[node] = ans;
    return ans;
}

void dfs2(int node, int p){
    if(node == 1){
        possible[node] = 1;
    }
    else{
        possible[node] = ((subTree[node] >= arr[p]) && possible[p]);
    }
    if(!possible[node]) return;
    for(int to:g[node]){
        if(to == p) continue;
        dfs2(to, node);
    }
}

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){
        dfs1(1, 1);
        dfs2(1, 1);
        for (int i = 1; i <= n; i++)
        {
            cout << possible[i];
        }
        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 237 ms 5060 KB Output is correct
5 Correct 214 ms 5076 KB Output is correct
6 Correct 378 ms 5080 KB Output is correct
7 Correct 241 ms 5092 KB Output is correct
8 Correct 189 ms 5080 KB Output is correct
9 Correct 321 ms 5128 KB Output is correct
10 Correct 116 ms 5092 KB Output is correct
11 Correct 109 ms 5088 KB Output is correct
12 Correct 133 ms 5092 KB Output is correct
13 Correct 183 ms 5084 KB Output is correct
14 Correct 134 ms 5104 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Incorrect 284 ms 15768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Incorrect 303 ms 19844 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 Execution timed out 1069 ms 195056 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 2 ms 4948 KB Output is correct
4 Correct 237 ms 5060 KB Output is correct
5 Correct 214 ms 5076 KB Output is correct
6 Correct 378 ms 5080 KB Output is correct
7 Correct 241 ms 5092 KB Output is correct
8 Correct 189 ms 5080 KB Output is correct
9 Correct 321 ms 5128 KB Output is correct
10 Correct 116 ms 5092 KB Output is correct
11 Correct 109 ms 5088 KB Output is correct
12 Correct 133 ms 5092 KB Output is correct
13 Correct 183 ms 5084 KB Output is correct
14 Correct 134 ms 5104 KB Output is correct
15 Correct 5 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Incorrect 284 ms 15768 KB Output isn't correct
18 Halted 0 ms 0 KB -