Submission #489863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
489863	2021-11-25T01:54:51 Z	SirCovidThe19th	Pipes (BOI13_pipes)	C++17	70.1852 / 100	448 ms	106720 KB

pipes

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define pii pair<int, int>
#define f first
#define s second

const int mx = 1e5 + 5;

int n, m, cnt; long long A[mx], ans[mx], altSm; bool vis[mx]; set<pii> adj[mx]; 

void compressLeaves(){
    queue<int> q; 
    FOR(i, 0, n) if (adj[i].size() == 1) q.push(i);
    while (!q.empty()){
        int cur = q.front(); q.pop();
        if (adj[cur].empty()) continue;

        pii nxt = *adj[cur].begin(); 
        ans[nxt.s] = A[cur]; A[nxt.f] -= A[cur];
        adj[cur].clear(); adj[nxt.f].erase({cur, nxt.s}); 
        if (adj[nxt.f].size() == 1) q.push(nxt.f);
    }
}
void dfs(int cur, bool parity){
    altSm += !parity ? A[cur] : -A[cur]; vis[cur] = 1;
    for (pii nxt : adj[cur]) if (!vis[nxt.f]) dfs(nxt.f, !parity);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> m;
    FOR(i, 0, n) cin >> A[i], A[i] *= 2;
    FOR(i, 0, m){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].insert({b, i}); adj[b].insert({a, i});
    }
    compressLeaves();

    FOR(i, 0, n){
        if (adj[i].size() == 2) cnt++;
        if (adj[i].size() > 2){ cout<<0<<"\n"; return 0; }
    }
    if (cnt and cnt % 2 == 0){ cout<<0<<"\n"; return 0; }

    FOR(i, 0, n) if (adj[i].size()){
        dfs(i, 0);
        pii rem = *prev(adj[i].end()); 

        A[i] -= altSm / 2; A[rem.s] -= altSm / 2;
        ans[rem.s] = altSm / 2;
        adj[i].erase(rem); adj[rem.f].erase({i, rem.s});

        compressLeaves();
    }
    FOR(i, 0, m) cout<<ans[i]<<"\n";
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	5068 KB	Output is correct
4	Correct	110 ms	16512 KB	Output is correct
5	Correct	2 ms	4940 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	4940 KB	Output is correct
8	Correct	2 ms	4940 KB	Output is correct
9	Correct	3 ms	5068 KB	Output is correct
10	Correct	3 ms	5068 KB	Output is correct
11	Correct	3 ms	5068 KB	Output is correct
12	Correct	3 ms	5068 KB	Output is correct
13	Correct	74 ms	14156 KB	Output is correct
14	Correct	85 ms	16000 KB	Output is correct
15	Correct	112 ms	16604 KB	Output is correct
16	Correct	80 ms	14832 KB	Output is correct
17	Correct	101 ms	16456 KB	Output is correct
18	Correct	92 ms	16588 KB	Output is correct
19	Correct	81 ms	16372 KB	Output is correct
20	Correct	2 ms	4940 KB	Output is correct
21	Correct	3 ms	5068 KB	Output is correct
22	Correct	114 ms	16524 KB	Output is correct
23	Correct	67 ms	14148 KB	Output is correct
24	Correct	92 ms	16472 KB	Output is correct
25	Correct	72 ms	14576 KB	Output is correct

Subtask #2

40.1851851852 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	4940 KB	Output isn't correct
2	Incorrect	3 ms	5068 KB	Output isn't correct
3	Correct	79 ms	15448 KB	Output is correct
4	Correct	93 ms	15996 KB	Output is correct
5	Correct	76 ms	15816 KB	Output is correct
6	Runtime error	387 ms	106720 KB	Execution killed with signal 11
7	Incorrect	3 ms	4940 KB	Output isn't correct
8	Incorrect	4 ms	4940 KB	Output isn't correct
9	Correct	3 ms	4940 KB	Output is correct
10	Correct	2 ms	4940 KB	Output is correct
11	Correct	2 ms	4940 KB	Output is correct
12	Correct	2 ms	4940 KB	Output is correct
13	Correct	2 ms	4940 KB	Output is correct
14	Incorrect	2 ms	4940 KB	Output isn't correct
15	Incorrect	3 ms	5068 KB	Output isn't correct
16	Incorrect	3 ms	5068 KB	Output isn't correct
17	Correct	3 ms	5068 KB	Output is correct
18	Correct	3 ms	5068 KB	Output is correct
19	Correct	3 ms	5104 KB	Output is correct
20	Correct	3 ms	5068 KB	Output is correct
21	Correct	3 ms	5196 KB	Output is correct
22	Incorrect	3 ms	5068 KB	Output isn't correct
23	Incorrect	92 ms	16852 KB	Output isn't correct
24	Incorrect	133 ms	19040 KB	Output isn't correct
25	Correct	82 ms	15424 KB	Output is correct
26	Correct	59 ms	15988 KB	Output is correct
27	Correct	63 ms	15860 KB	Output is correct
28	Correct	78 ms	16556 KB	Output is correct
29	Runtime error	288 ms	87896 KB	Execution killed with signal 11
30	Incorrect	92 ms	18344 KB	Output isn't correct
31	Incorrect	94 ms	20596 KB	Output isn't correct
32	Incorrect	93 ms	17440 KB	Output isn't correct
33	Correct	77 ms	15992 KB	Output is correct
34	Correct	64 ms	15992 KB	Output is correct
35	Correct	74 ms	16068 KB	Output is correct
36	Correct	77 ms	16148 KB	Output is correct
37	Runtime error	424 ms	106672 KB	Execution killed with signal 11
38	Incorrect	109 ms	18644 KB	Output isn't correct
39	Incorrect	96 ms	17036 KB	Output isn't correct
40	Incorrect	100 ms	18828 KB	Output isn't correct
41	Correct	73 ms	15940 KB	Output is correct
42	Correct	52 ms	15932 KB	Output is correct
43	Correct	53 ms	15892 KB	Output is correct
44	Correct	76 ms	15716 KB	Output is correct
45	Correct	448 ms	47040 KB	Output is correct
46	Incorrect	80 ms	18300 KB	Output isn't correct
47	Incorrect	95 ms	18932 KB	Output isn't correct
48	Incorrect	118 ms	20376 KB	Output isn't correct
49	Correct	88 ms	15428 KB	Output is correct
50	Correct	60 ms	16020 KB	Output is correct
51	Correct	71 ms	15988 KB	Output is correct
52	Correct	59 ms	15828 KB	Output is correct
53	Correct	377 ms	47996 KB	Output is correct
54	Incorrect	81 ms	18116 KB	Output isn't correct