oj.uz

Submission #79871

# Submission time Handle Problem Language Result Execution time Memory
79871 2018-10-17T02:57:59 Z win11905 Pipes (BOI13_pipes) C++11
22.8 / 100
 1000 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), g[u].clear();
            A[v] -= A[u];
            ans[x] = A[u] << 1;
            if(g[v].size() == 1) Q.emplace(v);
        }
    }
}

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];
    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;
                g[u].erase(i), g[v].erase(i);
                return;
            }
            dfs(v, u);
        }
    }
            
}

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:56: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:57: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:59: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
22.8 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5116 KB Output is correct
2 Correct 6 ms 5232 KB Output is correct
3 Correct 8 ms 5232 KB Output is correct
4 Execution timed out 1082 ms 17972 KB Time limit exceeded
5 Correct 6 ms 17972 KB Output is correct
6 Correct 6 ms 17972 KB Output is correct
7 Correct 6 ms 17972 KB Output is correct
8 Correct 6 ms 17972 KB Output is correct
9 Correct 9 ms 17972 KB Output is correct
10 Correct 7 ms 17972 KB Output is correct
11 Correct 7 ms 17972 KB Output is correct
12 Correct 7 ms 17972 KB Output is correct
13 Correct 118 ms 17972 KB Output is correct
14 Correct 159 ms 20532 KB Output is correct
15 Runtime error 109 ms 38760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 125 ms 38760 KB Output is correct
17 Execution timed out 1074 ms 41652 KB Time limit exceeded
18 Execution timed out 1073 ms 43208 KB Time limit exceeded
19 Correct 144 ms 45312 KB Output is correct
20 Correct 7 ms 45312 KB Output is correct
21 Correct 7 ms 45312 KB Output is correct
22 Runtime error 116 ms 46516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Correct 152 ms 46516 KB Output is correct
24 Execution timed out 1074 ms 49240 KB Time limit exceeded
25 Correct 127 ms 49240 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 49240 KB Output isn't correct
2 Runtime error 202 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 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.
4 Runtime error 96 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 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.
6 Runtime error 259 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 142 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 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.
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 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.
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 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.
14 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.
15 Runtime error 157 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 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.
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 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.
21 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.
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 606 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 593 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 110 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 87 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 97 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 123 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 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.
30 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.
31 Execution timed out 1081 ms 132096 KB Time limit exceeded
32 Runtime error 431 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 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.
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 131 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 267 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 692 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 150 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 Execution timed out 1034 ms 132096 KB Time limit exceeded
41 Execution timed out 1083 ms 132096 KB Time limit exceeded
42 Runtime error 115 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 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.
44 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.
45 Runtime error 201 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 472 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 99 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 734 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 131 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 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.
51 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.
52 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.
53 Runtime error 225 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 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.