oj.uz

답안 #697795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697795 2023-02-11T05:59:58 Z vjudge1 Stranded Far From Home (BOI22_island) C++14
20 / 100
 1000 ms 30536 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 2e5 + 7;

int n, m;
ll mx;
ll s[N];
vector <int> d[N];

namespace sub14 {
    vector <int> save;
    bool vis[N];

    bool check(int st) {
        priority_queue <pii, vector <pii>, greater <pii>> q;
        for (int i: save) vis[i] = false;
        save.clear();
        for (int u: d[st]) {
            vis[u] = true;
            save.push_back(u);
            q.push({s[u], u});
        }

        ll cur = s[st];
        vis[st] = true;
        save.push_back(st);
        ll tar = mx;
        while (q.size()) {
            int u = q.top().nd, w = q.top().st; q.pop();
            if (cur < w) return false;
            cur += w;
            if (cur >= tar) return true;

            for (int v: d[u]) if (!vis[v]) {
                vis[v] = true;
                save.push_back(v);
                q.push({s[v], v});
            }
        }

        return true;
    }
}

namespace sub2 {

    bool ck[N];
    ll f[N];

    void dfs(int p, int u) {
        f[u] = s[u];
        for (int v: d[u]) if (v != p) {
            dfs(u, v);
            f[u] += f[v];
        }

        ck[u] = f[u] >= s[p];
    }

    void dfs2(int p, int u) {
        for (int v: d[u]) if (v != p) {
            ck[v] &= ck[u];
            dfs2(u, v);
        }
    }

    void solve() {
        ck[1] = true;
        dfs(1, 1);
        dfs2(1, 1);
        rep(i, 1, n) cout << ck[i];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    rep(i, 1, n) {
        cin >> s[i];
        mx = max(mx, s[i]);
    }

    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        d[u].push_back(v);
        d[v].push_back(u);
    }

    bool is_sub2 = true;
    if (m != n - 1) is_sub2 = false;
    rep(i, 2, n) if (s[i] > s[i - 1]) is_sub2 = false;

    if (is_sub2) {
        sub2::solve();
        return 0;
    }

    rep(i, 1, n)
        cout << sub14 :: check(i);

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 227 ms 5152 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 128 ms 5076 KB Output is correct
14 Correct 86 ms 5128 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 131 ms 21040 KB Output is correct
4 Correct 121 ms 20940 KB Output is correct
5 Correct 149 ms 14540 KB Output is correct
6 Correct 162 ms 14972 KB Output is correct
7 Correct 167 ms 14884 KB Output is correct
8 Correct 166 ms 14896 KB Output is correct
9 Correct 134 ms 14756 KB Output is correct
10 Correct 88 ms 15580 KB Output is correct
11 Correct 83 ms 15572 KB Output is correct
12 Correct 146 ms 14932 KB Output is correct
13 Correct 129 ms 30440 KB Output is correct
14 Correct 137 ms 30536 KB Output is correct
15 Correct 154 ms 30400 KB Output is correct
16 Correct 83 ms 30084 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 144 ms 13260 KB Output is correct
3 Correct 143 ms 13128 KB Output is correct
4 Correct 140 ms 30352 KB Output is correct
5 Execution timed out 1087 ms 14056 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 160 ms 13244 KB Output is correct
3 Correct 188 ms 13240 KB Output is correct
4 Correct 190 ms 13252 KB Output is correct
5 Correct 143 ms 13260 KB Output is correct
6 Correct 146 ms 12788 KB Output is correct
7 Correct 135 ms 19496 KB Output is correct
8 Execution timed out 1080 ms 17556 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 227 ms 5152 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 128 ms 5076 KB Output is correct
14 Correct 86 ms 5128 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 131 ms 21040 KB Output is correct
18 Correct 121 ms 20940 KB Output is correct
19 Correct 149 ms 14540 KB Output is correct
20 Correct 162 ms 14972 KB Output is correct
21 Correct 167 ms 14884 KB Output is correct
22 Correct 166 ms 14896 KB Output is correct
23 Correct 134 ms 14756 KB Output is correct
24 Correct 88 ms 15580 KB Output is correct
25 Correct 83 ms 15572 KB Output is correct
26 Correct 146 ms 14932 KB Output is correct
27 Correct 129 ms 30440 KB Output is correct
28 Correct 137 ms 30536 KB Output is correct
29 Correct 154 ms 30400 KB Output is correct
30 Correct 83 ms 30084 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Correct 144 ms 13260 KB Output is correct
33 Correct 143 ms 13128 KB Output is correct
34 Correct 140 ms 30352 KB Output is correct
35 Execution timed out 1087 ms 14056 KB Time limit exceeded
36 Halted 0 ms 0 KB -