답안 #677757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677757	2023-01-04T10:03:09 Z	dooompy	Pipes (BOI13_pipes)	C++17	72.7778 / 100	148 ms	17688 KB

pipes

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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