oj.uz

Submission #722967

# Submission time Handle Problem Language Result Execution time Memory
722967 2023-04-13T06:33:03 Z dxz05 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 12028 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 = 200500;

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 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 61 ms 5096 KB Output is correct
5 Correct 59 ms 5076 KB Output is correct
6 Correct 81 ms 5196 KB Output is correct
7 Correct 61 ms 5076 KB Output is correct
8 Correct 44 ms 5076 KB Output is correct
9 Correct 130 ms 5076 KB Output is correct
10 Correct 54 ms 5076 KB Output is correct
11 Correct 52 ms 5076 KB Output is correct
12 Correct 39 ms 5076 KB Output is correct
13 Correct 87 ms 5084 KB Output is correct
14 Correct 37 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 Execution timed out 1080 ms 11976 KB Time limit exceeded
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 Execution timed out 1069 ms 11920 KB Time limit exceeded
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 1067 ms 12028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 3 ms 5024 KB Output is correct
4 Correct 61 ms 5096 KB Output is correct
5 Correct 59 ms 5076 KB Output is correct
6 Correct 81 ms 5196 KB Output is correct
7 Correct 61 ms 5076 KB Output is correct
8 Correct 44 ms 5076 KB Output is correct
9 Correct 130 ms 5076 KB Output is correct
10 Correct 54 ms 5076 KB Output is correct
11 Correct 52 ms 5076 KB Output is correct
12 Correct 39 ms 5076 KB Output is correct
13 Correct 87 ms 5084 KB Output is correct
14 Correct 37 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 Execution timed out 1080 ms 11976 KB Time limit exceeded
18 Halted 0 ms 0 KB -