oj.uz

답안 #677755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677755 2023-01-04T10:01:25 Z dooompy Pipes (BOI13_pipes) C++17
42.7778 / 100
 170 ms 18880 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;

        auto to = adj[cur][0];
        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);
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:66:18: warning: statement has no effect [-Wunused-value]
   66 |         deg[cur] == 0;
      |         ~~~~~~~~~^~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2680 KB Output isn't correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Incorrect 2 ms 2688 KB Output isn't correct
4 Incorrect 55 ms 10060 KB Output isn't correct
5 Incorrect 2 ms 2596 KB Output isn't correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Incorrect 2 ms 2748 KB Output isn't correct
8 Incorrect 3 ms 2684 KB Output isn't correct
9 Incorrect 3 ms 2644 KB Output isn't correct
10 Incorrect 2 ms 2772 KB Output isn't correct
11 Incorrect 2 ms 2696 KB Output isn't correct
12 Incorrect 2 ms 2696 KB Output isn't correct
13 Incorrect 37 ms 8760 KB Output isn't correct
14 Incorrect 54 ms 9788 KB Output isn't correct
15 Incorrect 49 ms 10172 KB Output isn't correct
16 Incorrect 46 ms 9204 KB Output isn't correct
17 Incorrect 57 ms 10120 KB Output isn't correct
18 Incorrect 50 ms 10144 KB Output isn't correct
19 Incorrect 45 ms 9300 KB Output isn't correct
20 Incorrect 2 ms 2684 KB Output isn't correct
21 Incorrect 2 ms 2644 KB Output isn't correct
22 Incorrect 59 ms 10176 KB Output isn't correct
23 Incorrect 39 ms 8780 KB Output isn't correct
24 Incorrect 53 ms 10160 KB Output isn't correct
25 Incorrect 41 ms 9128 KB Output isn't correct

Subtask #2
42.7777777778 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2684 KB Output isn't correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Correct 46 ms 9172 KB Output is correct
4 Correct 45 ms 9144 KB Output is correct
5 Correct 46 ms 9392 KB Output is correct
6 Correct 169 ms 18880 KB Output is correct
7 Incorrect 2 ms 2644 KB Output isn't correct
8 Runtime error 4 ms 5332 KB Execution killed with signal 6
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2680 KB Output is correct
12 Correct 2 ms 2624 KB Output is correct
13 Correct 2 ms 2684 KB Output is correct
14 Incorrect 1 ms 2644 KB Output isn't correct
15 Incorrect 3 ms 2644 KB Output isn't correct
16 Runtime error 5 ms 5332 KB Execution killed with signal 6
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2708 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 48 ms 15456 KB Execution killed with signal 6
24 Incorrect 41 ms 9328 KB Output isn't correct
25 Correct 39 ms 9128 KB Output is correct
26 Correct 46 ms 9328 KB Output is correct
27 Correct 42 ms 9032 KB Output is correct
28 Correct 50 ms 9552 KB Output is correct
29 Correct 139 ms 16872 KB Output is correct
30 Incorrect 37 ms 8892 KB Output isn't correct
31 Runtime error 49 ms 17076 KB Execution killed with signal 6
32 Runtime error 70 ms 18228 KB Execution killed with signal 6
33 Correct 57 ms 9356 KB Output is correct
34 Correct 55 ms 9124 KB Output is correct
35 Correct 44 ms 9192 KB Output is correct
36 Correct 40 ms 9512 KB Output is correct
37 Correct 170 ms 18852 KB Output is correct
38 Incorrect 42 ms 9164 KB Output isn't correct
39 Runtime error 46 ms 18252 KB Execution killed with signal 6
40 Incorrect 41 ms 9352 KB Output isn't correct
41 Runtime error 43 ms 17120 KB Execution killed with signal 6
42 Correct 43 ms 8956 KB Output is correct
43 Correct 44 ms 8956 KB Output is correct
44 Correct 50 ms 9440 KB Output is correct
45 Correct 107 ms 16740 KB Output is correct
46 Incorrect 42 ms 8908 KB Output isn't correct
47 Incorrect 44 ms 9360 KB Output isn't correct
48 Runtime error 42 ms 17108 KB Execution killed with signal 6
49 Correct 39 ms 9408 KB Output is correct
50 Correct 41 ms 9164 KB Output is correct
51 Correct 43 ms 9428 KB Output is correct
52 Correct 37 ms 9072 KB Output is correct
53 Correct 131 ms 16588 KB Output is correct
54 Incorrect 41 ms 9076 KB Output isn't correct