oj.uz

Submission #677757

# Submission time Handle Problem Language Result Execution time Memory
677757 2023-01-04T10:03:09 Z dooompy Pipes (BOI13_pipes) C++17
72.7778 / 100
 148 ms 17688 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

ll v[100005];
int deg[100005];

vector<pair<int, int>> adj[100005];
ll calc[500005];

bool seen[100005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        deg[a]++; deg[b]++;
    }

    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        // deg 1
        auto cur = q.front(); q.pop();
        seen[cur] = true;
        deg[cur] = 0;
        
        for (auto to : adj[cur]) {
            if (seen[to.first]) continue;
            ll weight = v[cur];

            v[to.first] -= weight;
            calc[to.second] = weight;

            if (--deg[to.first] == 1) {
                q.push(to.first);
            }
        }
    }

    if (m == n - 1) {
        for (int i = 1; i <= m; i++) {
            cout << calc[i] * 2 << "\n";
        }
        return 0;
    }

    if (m > n || m % 2 == 0) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        assert(deg[i] == 2);
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 52 ms 9036 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 39 ms 7704 KB Output is correct
14 Correct 57 ms 8704 KB Output is correct
15 Correct 53 ms 9064 KB Output is correct
16 Correct 40 ms 8068 KB Output is correct
17 Correct 55 ms 9036 KB Output is correct
18 Correct 51 ms 9112 KB Output is correct
19 Correct 51 ms 8360 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 49 ms 9032 KB Output is correct
23 Correct 42 ms 7740 KB Output is correct
24 Correct 49 ms 9064 KB Output is correct
25 Correct 47 ms 8012 KB Output is correct

Subtask #2
42.7777777778 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Correct 42 ms 8008 KB Output is correct
4 Correct 38 ms 7988 KB Output is correct
5 Correct 60 ms 8268 KB Output is correct
6 Correct 147 ms 17676 KB Output is correct
7 Incorrect 1 ms 2644 KB Output isn't correct
8 Runtime error 6 ms 5204 KB Execution killed with signal 6
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Incorrect 2 ms 2644 KB Output isn't correct
15 Incorrect 2 ms 2644 KB Output isn't correct
16 Runtime error 4 ms 5332 KB Execution killed with signal 6
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2772 KB Output is correct
22 Incorrect 2 ms 2644 KB Output isn't correct
23 Runtime error 38 ms 14288 KB Execution killed with signal 6
24 Incorrect 41 ms 8128 KB Output isn't correct
25 Correct 41 ms 8000 KB Output is correct
26 Correct 44 ms 8040 KB Output is correct
27 Correct 37 ms 7840 KB Output is correct
28 Correct 45 ms 8452 KB Output is correct
29 Correct 129 ms 15560 KB Output is correct
30 Incorrect 43 ms 7828 KB Output isn't correct
31 Runtime error 46 ms 16068 KB Execution killed with signal 6
32 Runtime error 50 ms 17144 KB Execution killed with signal 6
33 Correct 39 ms 8156 KB Output is correct
34 Correct 37 ms 8008 KB Output is correct
35 Correct 37 ms 8012 KB Output is correct
36 Correct 41 ms 8276 KB Output is correct
37 Correct 148 ms 17688 KB Output is correct
38 Incorrect 40 ms 8032 KB Output isn't correct
39 Runtime error 54 ms 17140 KB Execution killed with signal 6
40 Incorrect 39 ms 8168 KB Output isn't correct
41 Runtime error 40 ms 15864 KB Execution killed with signal 6
42 Correct 39 ms 7796 KB Output is correct
43 Correct 40 ms 7756 KB Output is correct
44 Correct 43 ms 8348 KB Output is correct
45 Correct 120 ms 15688 KB Output is correct
46 Incorrect 40 ms 7764 KB Output isn't correct
47 Incorrect 44 ms 8152 KB Output isn't correct
48 Runtime error 54 ms 16000 KB Execution killed with signal 6
49 Correct 43 ms 8256 KB Output is correct
50 Correct 43 ms 8044 KB Output is correct
51 Correct 39 ms 8172 KB Output is correct
52 Correct 35 ms 7880 KB Output is correct
53 Correct 119 ms 15552 KB Output is correct
54 Incorrect 46 ms 7980 KB Output isn't correct