oj.uz

Submission #794377

# Submission time Handle Problem Language Result Execution time Memory
794377 2023-07-26T13:40:01 Z TahirAliyev Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 13608 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
#define ll long long int
#define oo 4e18
#define pii pair<int, int>

const int MAX = 2e5 + 5;

int arr[MAX];
int ans[MAX];
vector<int> g[MAX];
bool collected[MAX];

bool djikstra(int node){
    memset(collected, 0, sizeof(collected));
    ll sum = arr[node];
    collected[node] = 1;
    set<pii> s;
    for(int to : g[node]){
        s.insert({arr[to], to});
    }
    while(!s.empty()){
        pii a = *(s.begin());
        if(a.first > sum){
            return 0;
        }
        sum += a.first;
        collected[a.second] = 1;
        s.erase(s.begin());
        for(int to : g[a.second]){
            if(collected[to]) continue;
            s.insert({arr[to], to});
        }
    }
    return 1;
}

int main(){
    int n, m; 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].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << djikstra(i);
    }
    
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 205 ms 5272 KB Output is correct
5 Correct 182 ms 5304 KB Output is correct
6 Correct 304 ms 5204 KB Output is correct
7 Correct 191 ms 5204 KB Output is correct
8 Correct 156 ms 5280 KB Output is correct
9 Correct 256 ms 5332 KB Output is correct
10 Correct 88 ms 5204 KB Output is correct
11 Correct 87 ms 5304 KB Output is correct
12 Correct 107 ms 5296 KB Output is correct
13 Correct 199 ms 5288 KB Output is correct
14 Correct 112 ms 5292 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Execution timed out 1073 ms 13608 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Execution timed out 1086 ms 12168 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 5204 KB Output is correct
2 Execution timed out 1069 ms 12504 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 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 205 ms 5272 KB Output is correct
5 Correct 182 ms 5304 KB Output is correct
6 Correct 304 ms 5204 KB Output is correct
7 Correct 191 ms 5204 KB Output is correct
8 Correct 156 ms 5280 KB Output is correct
9 Correct 256 ms 5332 KB Output is correct
10 Correct 88 ms 5204 KB Output is correct
11 Correct 87 ms 5304 KB Output is correct
12 Correct 107 ms 5296 KB Output is correct
13 Correct 199 ms 5288 KB Output is correct
14 Correct 112 ms 5292 KB Output is correct
15 Correct 2 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Execution timed out 1073 ms 13608 KB Time limit exceeded
18 Halted 0 ms 0 KB -