oj.uz

Submission #1098919

# Submission time Handle Problem Language Result Execution time Memory
1098919 2024-10-10T10:17:47 Z crafticat Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 16344 KB 
#include <bits/stdc++.h>

#include <utility>

using namespace std;
#define F0R(i, n) for (ll i= 0; i < n;i++)
template<typename T>
using V = vector<T>;
using ll = long long;
using vi = V<ll>;
using vvi = V<vi>;
#define pb push_back
using pi = pair<ll, ll>;
#define all(x) begin(x), end(x)
#define f first
#define s second
vvi g;

bool pos(ll x, vi sum) {
    priority_queue<pi,V<pi>, greater<>> nodes;
    nodes.push({sum[x], x});
    ll gs = -1;
    V<bool> vis(sum.size());
    ll visited = 0;

    while (!nodes.empty()) {
        auto [nodeS, a] = nodes.top(); nodes.pop();
        if (vis[a]) continue;
        vis[a] = true;
        if (nodeS > gs && gs != -1) return false;
        if (gs == -1) gs = 0;
        gs += nodeS;
        visited++;

        for (auto child : g[a]) {
            if (vis[child]) continue;
            nodes.emplace(sum[child], child);
        }
    }

    return visited == sum.size() - 1;
}

int main() {
    ll n, m; cin >> n >> m;
    vi init(n + 1);
    F0R(i, n)
        cin >> init[i + 1];

    g.resize(n + 1);

    F0R(i, m) {
        ll a, b; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    F0R(i, n)
        cout << pos(i + 1, init);
}

Compilation message

island.cpp: In function 'bool pos(ll, vi)':
island.cpp:41:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     return visited == sum.size() - 1;
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 159 ms 560 KB Output is correct
5 Correct 102 ms 604 KB Output is correct
6 Correct 194 ms 600 KB Output is correct
7 Correct 165 ms 600 KB Output is correct
8 Correct 129 ms 604 KB Output is correct
9 Correct 132 ms 604 KB Output is correct
10 Correct 31 ms 604 KB Output is correct
11 Correct 28 ms 604 KB Output is correct
12 Correct 32 ms 604 KB Output is correct
13 Correct 56 ms 348 KB Output is correct
14 Correct 63 ms 604 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1093 ms 14280 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1089 ms 15540 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 159 ms 560 KB Output is correct
5 Correct 102 ms 604 KB Output is correct
6 Correct 194 ms 600 KB Output is correct
7 Correct 165 ms 600 KB Output is correct
8 Correct 129 ms 604 KB Output is correct
9 Correct 132 ms 604 KB Output is correct
10 Correct 31 ms 604 KB Output is correct
11 Correct 28 ms 604 KB Output is correct
12 Correct 32 ms 604 KB Output is correct
13 Correct 56 ms 348 KB Output is correct
14 Correct 63 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Execution timed out 1085 ms 16344 KB Time limit exceeded
18 Halted 0 ms 0 KB -