답안 #445009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445009 2021-07-16T08:28:19 Z zxcvbnm Pipes (BOI13_pipes) C++14
30 / 100
221 ms 42584 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 1e5 + 5;
vector<int> need, curr;
vector<pair<int, int>> adj[maxN];
vector<int> in;
vector<int> ans;
void bfs(int n) {
    queue<int> q;
    vector<bool> vis(n, false);
    for(int i = 0; i < n; i++) {
        if (in[i] == 1) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = true;

        for(auto u : adj[v]) {
            if (vis[u.first]) continue;

            ans[u.second] = (need[v] - curr[v]) * 2;
            curr[u.first] += ans[u.second] / 2;
            curr[v] += ans[u.second] / 2;

            in[u.first]--;
            if (in[u.first] == 1) {
                q.push(u.first);
            }
        }
        assert(curr[v] == need[v]);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    need.resize(n);
    curr.assign(n, 0);
    in.assign(n, 0);
    ans.assign(n, 0);
    for(int& i : need) {
        cin >> i;
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back({y, i});
        adj[y].push_back({x, i});
        in[x]++;
        in[y]++;
    }

    bfs(n);
    for(int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2664 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 71 ms 10068 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2672 KB Output is correct
13 Correct 55 ms 8560 KB Output is correct
14 Correct 66 ms 9664 KB Output is correct
15 Correct 73 ms 10184 KB Output is correct
16 Correct 58 ms 8996 KB Output is correct
17 Correct 70 ms 10180 KB Output is correct
18 Correct 71 ms 10180 KB Output is correct
19 Correct 72 ms 9540 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 3 ms 2708 KB Output is correct
22 Correct 77 ms 10140 KB Output is correct
23 Correct 54 ms 8552 KB Output is correct
24 Correct 72 ms 10148 KB Output is correct
25 Correct 59 ms 8896 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Incorrect 62 ms 9264 KB Output isn't correct
4 Incorrect 63 ms 9288 KB Output isn't correct
5 Incorrect 72 ms 9684 KB Output isn't correct
6 Runtime error 215 ms 42360 KB Execution killed with signal 11
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 2 ms 2636 KB Output isn't correct
9 Incorrect 2 ms 2636 KB Output isn't correct
10 Incorrect 2 ms 2636 KB Output isn't correct
11 Incorrect 2 ms 2636 KB Output isn't correct
12 Runtime error 5 ms 5196 KB Execution killed with signal 6
13 Incorrect 2 ms 2636 KB Output isn't correct
14 Incorrect 2 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2636 KB Output isn't correct
16 Incorrect 2 ms 2668 KB Output isn't correct
17 Incorrect 2 ms 2636 KB Output isn't correct
18 Incorrect 2 ms 2636 KB Output isn't correct
19 Incorrect 2 ms 2700 KB Output isn't correct
20 Runtime error 5 ms 5324 KB Execution killed with signal 11
21 Incorrect 3 ms 2764 KB Output isn't correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Incorrect 52 ms 8260 KB Output isn't correct
24 Incorrect 68 ms 9592 KB Output isn't correct
25 Incorrect 64 ms 9284 KB Output isn't correct
26 Incorrect 69 ms 9540 KB Output isn't correct
27 Incorrect 61 ms 9296 KB Output isn't correct
28 Runtime error 82 ms 17212 KB Execution killed with signal 11
29 Incorrect 221 ms 21620 KB Output isn't correct
30 Incorrect 67 ms 9112 KB Output isn't correct
31 Incorrect 62 ms 9320 KB Output isn't correct
32 Incorrect 70 ms 9924 KB Output isn't correct
33 Incorrect 70 ms 9568 KB Output isn't correct
34 Incorrect 61 ms 9244 KB Output isn't correct
35 Incorrect 61 ms 9284 KB Output isn't correct
36 Runtime error 78 ms 17000 KB Execution killed with signal 6
37 Runtime error 218 ms 42584 KB Execution killed with signal 11
38 Incorrect 67 ms 9412 KB Output isn't correct
39 Incorrect 71 ms 9984 KB Output isn't correct
40 Incorrect 66 ms 9632 KB Output isn't correct
41 Incorrect 65 ms 9216 KB Output isn't correct
42 Incorrect 64 ms 9088 KB Output isn't correct
43 Incorrect 57 ms 9156 KB Output isn't correct
44 Incorrect 66 ms 9660 KB Output isn't correct
45 Runtime error 185 ms 37744 KB Execution killed with signal 11
46 Incorrect 65 ms 9284 KB Output isn't correct
47 Incorrect 66 ms 9600 KB Output isn't correct
48 Incorrect 67 ms 9384 KB Output isn't correct
49 Incorrect 64 ms 9608 KB Output isn't correct
50 Incorrect 63 ms 9496 KB Output isn't correct
51 Incorrect 63 ms 9664 KB Output isn't correct
52 Incorrect 60 ms 9244 KB Output isn't correct
53 Runtime error 202 ms 38052 KB Execution killed with signal 11
54 Incorrect 65 ms 9412 KB Output isn't correct