oj.uz

Submission #79877

# Submission time Handle Problem Language Result Execution time Memory
79877 2018-10-17T03:12:40 Z win11905 Pipes (BOI13_pipes) C++11
83.1481 / 100
 210 ms 97020 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);
}

queue<int> Q;

void solve() {
    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 == idx) {
                ans[i] = sum;
                A[u] -= sum / 2, A[v] -= sum / 2;
                z = i;
                break;
            }
            dfs(v, u);
        }
    }
    if(cnt == idx) {
        int v = u ^ s[z] ^ t[z];
        g[v].erase(z), g[u].erase(z);
        Q.emplace(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;
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) Q.emplace(i);
    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:62: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:63: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:65: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 5084 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5200 KB Output is correct
4 Correct 146 ms 18640 KB Output is correct
5 Correct 6 ms 18640 KB Output is correct
6 Correct 6 ms 18640 KB Output is correct
7 Correct 6 ms 18640 KB Output is correct
8 Correct 6 ms 18640 KB Output is correct
9 Correct 7 ms 18640 KB Output is correct
10 Correct 7 ms 18640 KB Output is correct
11 Correct 7 ms 18640 KB Output is correct
12 Correct 7 ms 18640 KB Output is correct
13 Correct 140 ms 18640 KB Output is correct
14 Correct 155 ms 20956 KB Output is correct
15 Correct 154 ms 23288 KB Output is correct
16 Correct 135 ms 23288 KB Output is correct
17 Correct 154 ms 26020 KB Output is correct
18 Correct 155 ms 27620 KB Output is correct
19 Correct 146 ms 28992 KB Output is correct
20 Correct 6 ms 28992 KB Output is correct
21 Correct 7 ms 28992 KB Output is correct
22 Correct 169 ms 30844 KB Output is correct
23 Correct 109 ms 30844 KB Output is correct
24 Correct 210 ms 33604 KB Output is correct
25 Correct 129 ms 33604 KB Output is correct

Subtask #2
53.1481481481 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 33604 KB Output isn't correct
2 Correct 7 ms 33604 KB Output is correct
3 Correct 137 ms 35388 KB Output is correct
4 Correct 92 ms 37064 KB Output is correct
5 Correct 95 ms 38480 KB Output is correct
6 Incorrect 125 ms 43776 KB Output isn't correct
7 Incorrect 6 ms 43776 KB Output isn't correct
8 Correct 6 ms 43776 KB Output is correct
9 Correct 6 ms 43776 KB Output is correct
10 Correct 6 ms 43776 KB Output is correct
11 Correct 6 ms 43776 KB Output is correct
12 Correct 6 ms 43776 KB Output is correct
13 Correct 6 ms 43776 KB Output is correct
14 Incorrect 6 ms 43776 KB Output isn't correct
15 Correct 7 ms 43776 KB Output is correct
16 Correct 7 ms 43776 KB Output is correct
17 Correct 6 ms 43776 KB Output is correct
18 Correct 6 ms 43776 KB Output is correct
19 Correct 6 ms 43776 KB Output is correct
20 Correct 6 ms 43776 KB Output is correct
21 Correct 8 ms 43776 KB Output is correct
22 Incorrect 6 ms 43776 KB Output isn't correct
23 Correct 129 ms 44516 KB Output is correct
24 Correct 171 ms 48528 KB Output is correct
25 Correct 111 ms 48528 KB Output is correct
26 Correct 91 ms 48528 KB Output is correct
27 Correct 85 ms 48528 KB Output is correct
28 Correct 124 ms 50184 KB Output is correct
29 Correct 147 ms 51944 KB Output is correct
30 Incorrect 120 ms 53592 KB Output isn't correct
31 Correct 179 ms 62548 KB Output is correct
32 Correct 156 ms 62548 KB Output is correct
33 Correct 113 ms 62548 KB Output is correct
34 Correct 94 ms 62548 KB Output is correct
35 Correct 91 ms 62548 KB Output is correct
36 Correct 131 ms 62856 KB Output is correct
37 Incorrect 128 ms 67504 KB Output isn't correct
38 Correct 173 ms 70304 KB Output is correct
39 Incorrect 155 ms 70304 KB Output isn't correct
40 Incorrect 137 ms 70304 KB Output isn't correct
41 Correct 100 ms 70752 KB Output is correct
42 Correct 93 ms 72012 KB Output is correct
43 Correct 87 ms 73508 KB Output is correct
44 Correct 88 ms 74676 KB Output is correct
45 Incorrect 139 ms 78084 KB Output isn't correct
46 Correct 150 ms 79116 KB Output is correct
47 Incorrect 137 ms 79116 KB Output isn't correct
48 Correct 198 ms 82628 KB Output is correct
49 Correct 152 ms 82628 KB Output is correct
50 Correct 117 ms 82628 KB Output is correct
51 Correct 120 ms 82628 KB Output is correct
52 Correct 96 ms 82628 KB Output is correct
53 Runtime error 127 ms 97020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Incorrect 149 ms 97020 KB Output isn't correct