oj.uz

Submission #723303

# Submission time Handle Problem Language Result Execution time Memory
723303 2023-04-13T14:00:08 Z MurotY Stranded Far From Home (BOI22_island) C++14
20 / 100
 1000 ms 400684 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;
}
 
ll subTree[MAX];
bool possible[MAX];
void dfs1(int node, int p){
    ll ans = arr[node];
    for(int to:g[node]){
        if(to == p) continue;
        dfs1(to, node);
        ans += subTree[to];
    }
    subTree[node] = ans;
}
 
void dfs2(int node, int p){
    if(node == 1){
        possible[node] = 1;
    }
    else{
        possible[node] = (subTree[node] >= arr[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 3 ms 4932 KB Output is correct
4 Correct 220 ms 5080 KB Output is correct
5 Correct 200 ms 5080 KB Output is correct
6 Correct 336 ms 5080 KB Output is correct
7 Correct 217 ms 5076 KB Output is correct
8 Correct 176 ms 5076 KB Output is correct
9 Correct 302 ms 5116 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 95 ms 5076 KB Output is correct
12 Correct 115 ms 5076 KB Output is correct
13 Correct 185 ms 5076 KB Output is correct
14 Correct 108 ms 5080 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 295 ms 20212 KB Output is correct
4 Correct 243 ms 21380 KB Output is correct
5 Correct 312 ms 14980 KB Output is correct
6 Correct 309 ms 15364 KB Output is correct
7 Correct 318 ms 15384 KB Output is correct
8 Correct 328 ms 15584 KB Output is correct
9 Correct 289 ms 15224 KB Output is correct
10 Correct 220 ms 15980 KB Output is correct
11 Correct 221 ms 15940 KB Output is correct
12 Correct 255 ms 15308 KB Output is correct
13 Correct 234 ms 30636 KB Output is correct
14 Correct 247 ms 30640 KB Output is correct
15 Correct 298 ms 30884 KB Output is correct
16 Correct 216 ms 30664 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 288 ms 29428 KB Output isn't correct
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 1085 ms 400684 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 4932 KB Output is correct
4 Correct 220 ms 5080 KB Output is correct
5 Correct 200 ms 5080 KB Output is correct
6 Correct 336 ms 5080 KB Output is correct
7 Correct 217 ms 5076 KB Output is correct
8 Correct 176 ms 5076 KB Output is correct
9 Correct 302 ms 5116 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 95 ms 5076 KB Output is correct
12 Correct 115 ms 5076 KB Output is correct
13 Correct 185 ms 5076 KB Output is correct
14 Correct 108 ms 5080 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 295 ms 20212 KB Output is correct
18 Correct 243 ms 21380 KB Output is correct
19 Correct 312 ms 14980 KB Output is correct
20 Correct 309 ms 15364 KB Output is correct
21 Correct 318 ms 15384 KB Output is correct
22 Correct 328 ms 15584 KB Output is correct
23 Correct 289 ms 15224 KB Output is correct
24 Correct 220 ms 15980 KB Output is correct
25 Correct 221 ms 15940 KB Output is correct
26 Correct 255 ms 15308 KB Output is correct
27 Correct 234 ms 30636 KB Output is correct
28 Correct 247 ms 30640 KB Output is correct
29 Correct 298 ms 30884 KB Output is correct
30 Correct 216 ms 30664 KB Output is correct
31 Correct 4 ms 4948 KB Output is correct
32 Incorrect 288 ms 29428 KB Output isn't correct
33 Halted 0 ms 0 KB -