oj.uz

Submission #722966

# Submission time Handle Problem Language Result Execution time Memory
722966 2023-04-13T06:32:28 Z dxz05 Stranded Far From Home (BOI22_island) C++17
10 / 100
 126 ms 6044 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

int n;
vector<int> g[N];
int s[N];

bool check(int v){
    queue<int> q;
    q.push(v);
    vector<bool> used(n, false);
    used[v] = true;

    ll sum = 0;
    set<pair<int, int>> blocked;
    while (!q.empty()){
        v = q.front();
        q.pop();

        sum += s[v];

        while (!blocked.empty() && blocked.begin()->first <= sum){
            int x = blocked.begin()->second;
            q.push(x);
            used[x] = true;
            blocked.erase(blocked.begin());
        }

        for (int u : g[v]){
            if (used[u]) continue;
            if (s[u] <= sum){
                q.push(u);
                used[u] = true;
            } else {
                blocked.emplace(s[u], u);
            }
        }
    }

    return count(all(used), true) == n;
}

void solve(){
    int m;
    cin >> n >> m;

    for (int i = 0; i < n; i++){
        cin >> s[i];
    }

    while (m--){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 0; i < n; i++){
        cout << check(i);
    }
    cout << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 69 ms 2732 KB Output is correct
5 Correct 64 ms 2740 KB Output is correct
6 Correct 78 ms 2732 KB Output is correct
7 Correct 58 ms 2724 KB Output is correct
8 Correct 44 ms 2720 KB Output is correct
9 Correct 126 ms 2784 KB Output is correct
10 Correct 51 ms 2644 KB Output is correct
11 Correct 49 ms 2644 KB Output is correct
12 Correct 37 ms 2740 KB Output is correct
13 Correct 89 ms 2744 KB Output is correct
14 Correct 35 ms 2644 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Runtime error 22 ms 5964 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2572 KB Output is correct
2 Runtime error 22 ms 6044 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 22 ms 5960 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 69 ms 2732 KB Output is correct
5 Correct 64 ms 2740 KB Output is correct
6 Correct 78 ms 2732 KB Output is correct
7 Correct 58 ms 2724 KB Output is correct
8 Correct 44 ms 2720 KB Output is correct
9 Correct 126 ms 2784 KB Output is correct
10 Correct 51 ms 2644 KB Output is correct
11 Correct 49 ms 2644 KB Output is correct
12 Correct 37 ms 2740 KB Output is correct
13 Correct 89 ms 2744 KB Output is correct
14 Correct 35 ms 2644 KB Output is correct
15 Correct 2 ms 2680 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Runtime error 22 ms 5964 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -