oj.uz

Submission #79875

# Submission time Handle Problem Language Result Execution time Memory
79875 2018-10-17T03:07:34 Z win11905 Pipes (BOI13_pipes) C++11
30 / 100
 715 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;

int n, m, s[N], t[N];
int A[N], deg[N];
int ans[N];

set<int> g[N];

void answer() {
    for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    exit(0);
}

void solve() {
    queue<int> Q;
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) Q.emplace(i);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int x : g[u]) {
            int v = u ^ s[x] ^ t[x]; 
            g[v].erase(x);
            A[v] -= A[u];
            ans[x] = A[u] << 1;
            if(g[v].size() == 1) Q.emplace(v);
        }
        g[u].clear();
    }
}

int cnt = 0;

void dfs(int u, int p) {
    static int idx = 0;
    static int sum = 0;
    idx++;
    if(idx & 1) sum += A[u];
    else sum -= A[u];
    int z = -1;
    for(auto i : g[u]) {
        int v = u ^ s[i] ^ t[i];
        if(v != p) {
            if(cnt == sum) {
                ans[i] = sum;
                A[u] -= sum / 2, A[v] -= sum / 2;
                z = i;
                break;
            }
            dfs(v, u);
        }
    }
    if(cnt == sum) {
        int v = u ^ s[z] ^ t[z];
        g[v].erase(z), g[u].erase(z);
    } 
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", A+i);
    for(int i = 0; i < m; ++i) {
        scanf("%d %d", s+i, t+i);
        g[s[i]].emplace(i), g[t[i]].emplace(i);
        deg[s[i]]++, deg[t[i]]++;
    }
    if(n < m) return puts("0"), 0;
    solve(); 
    if(n == m+1) answer();
    for(int i = 1; i <= n; ++i) if(g[i].size()) cnt++;
    if(cnt % 2 == 0) return puts("0"), 0;
    for(int i = 1; i <= n; ++i) {
        if(g[i].size()) dfs(i, i);
        break;
    }
    solve();
    answer();
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:62:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~
pipes.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", s+i, t+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5448 KB Output is correct
4 Correct 158 ms 18256 KB Output is correct
5 Correct 6 ms 18256 KB Output is correct
6 Correct 6 ms 18256 KB Output is correct
7 Correct 6 ms 18256 KB Output is correct
8 Correct 6 ms 18256 KB Output is correct
9 Correct 7 ms 18256 KB Output is correct
10 Correct 7 ms 18256 KB Output is correct
11 Correct 7 ms 18256 KB Output is correct
12 Correct 7 ms 18256 KB Output is correct
13 Correct 125 ms 18256 KB Output is correct
14 Correct 156 ms 20604 KB Output is correct
15 Correct 174 ms 22852 KB Output is correct
16 Correct 141 ms 22852 KB Output is correct
17 Correct 197 ms 25724 KB Output is correct
18 Correct 177 ms 27300 KB Output is correct
19 Correct 138 ms 29164 KB Output is correct
20 Correct 6 ms 29164 KB Output is correct
21 Correct 7 ms 29164 KB Output is correct
22 Correct 157 ms 30496 KB Output is correct
23 Correct 128 ms 30496 KB Output is correct
24 Correct 185 ms 33232 KB Output is correct
25 Correct 134 ms 33232 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 33232 KB Output isn't correct
2 Runtime error 171 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 122 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
4 Runtime error 108 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5 Runtime error 117 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
6 Runtime error 279 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
8 Runtime error 127 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
10 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
11 Runtime error 9 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
12 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
13 Runtime error 7 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
14 Runtime error 7 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
15 Runtime error 167 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 7 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
17 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
18 Runtime error 7 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
19 Runtime error 7 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Runtime error 6 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
21 Runtime error 8 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
22 Runtime error 7 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
23 Runtime error 684 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 715 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 111 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
26 Runtime error 102 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
27 Runtime error 102 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
28 Runtime error 141 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Runtime error 117 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30 Runtime error 136 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
31 Runtime error 662 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 478 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 126 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
34 Runtime error 90 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
35 Runtime error 100 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
36 Runtime error 143 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
37 Runtime error 310 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 651 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 154 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
40 Runtime error 148 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
41 Runtime error 103 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
42 Runtime error 94 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
43 Runtime error 88 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
44 Runtime error 93 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
45 Runtime error 229 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 638 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 166 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
48 Runtime error 646 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 137 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
50 Runtime error 120 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
51 Runtime error 90 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
52 Runtime error 91 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
53 Runtime error 229 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 128 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.