Submission #489857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
489857	2021-11-25T01:48:03 Z	SirCovidThe19th	Pipes (BOI13_pipes)	C++17	70.1852 / 100	1000 ms	113000 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, st = -1, 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[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(){
    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) st = i, cnt++;
        if (adj[i].size() > 2){ cout<<0<<"\n"; return 0; }
    }
    if (cnt and cnt % 2 == 0){ cout<<0<<"\n"; return 0; }

    if (~st){
        dfs(st, 0);
        pii rem = *prev(adj[st].end()); 

        A[st] -= altSm / 2; A[rem.s] -= altSm / 2;
        ans[rem.s] = altSm / 2;
        adj[st].erase(rem); adj[rem.f].erase({st, 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	3 ms	4944 KB	Output is correct
2	Correct	3 ms	5000 KB	Output is correct
3	Correct	4 ms	5104 KB	Output is correct
4	Correct	146 ms	18108 KB	Output is correct
5	Correct	2 ms	4944 KB	Output is correct
6	Correct	3 ms	4944 KB	Output is correct
7	Correct	3 ms	4944 KB	Output is correct
8	Correct	3 ms	5000 KB	Output is correct
9	Correct	4 ms	5072 KB	Output is correct
10	Correct	3 ms	5072 KB	Output is correct
11	Correct	5 ms	5012 KB	Output is correct
12	Correct	3 ms	5072 KB	Output is correct
13	Correct	111 ms	15336 KB	Output is correct
14	Correct	138 ms	17372 KB	Output is correct
15	Correct	179 ms	18120 KB	Output is correct
16	Correct	128 ms	16048 KB	Output is correct
17	Correct	144 ms	17996 KB	Output is correct
18	Correct	158 ms	18088 KB	Output is correct
19	Correct	143 ms	17972 KB	Output is correct
20	Correct	3 ms	4944 KB	Output is correct
21	Correct	4 ms	5072 KB	Output is correct
22	Correct	155 ms	18068 KB	Output is correct
23	Correct	111 ms	15304 KB	Output is correct
24	Correct	165 ms	18236 KB	Output is correct
25	Correct	119 ms	15836 KB	Output is correct

Subtask #2

40.1851851852 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	4944 KB	Output isn't correct
2	Incorrect	3 ms	5072 KB	Output isn't correct
3	Correct	116 ms	16868 KB	Output is correct
4	Correct	116 ms	17504 KB	Output is correct
5	Correct	136 ms	17348 KB	Output is correct
6	Runtime error	578 ms	113000 KB	Execution killed with signal 11
7	Incorrect	3 ms	4944 KB	Output isn't correct
8	Incorrect	3 ms	4996 KB	Output isn't correct
9	Correct	3 ms	4944 KB	Output is correct
10	Correct	3 ms	4944 KB	Output is correct
11	Correct	4 ms	4944 KB	Output is correct
12	Correct	3 ms	4944 KB	Output is correct
13	Correct	3 ms	5004 KB	Output is correct
14	Incorrect	3 ms	5000 KB	Output isn't correct
15	Incorrect	4 ms	5072 KB	Output isn't correct
16	Incorrect	4 ms	5140 KB	Output isn't correct
17	Correct	3 ms	5072 KB	Output is correct
18	Correct	4 ms	5072 KB	Output is correct
19	Correct	3 ms	5072 KB	Output is correct
20	Correct	3 ms	5072 KB	Output is correct
21	Correct	4 ms	5200 KB	Output is correct
22	Incorrect	10 ms	5072 KB	Output isn't correct
23	Incorrect	178 ms	18640 KB	Output isn't correct
24	Incorrect	188 ms	21196 KB	Output isn't correct
25	Correct	117 ms	16896 KB	Output is correct
26	Correct	121 ms	17572 KB	Output is correct
27	Correct	105 ms	17356 KB	Output is correct
28	Correct	131 ms	18264 KB	Output is correct
29	Runtime error	475 ms	92872 KB	Execution killed with signal 11
30	Execution timed out	1080 ms	19656 KB	Time limit exceeded
31	Incorrect	225 ms	22892 KB	Output isn't correct
32	Incorrect	203 ms	19364 KB	Output isn't correct
33	Correct	137 ms	17608 KB	Output is correct
34	Correct	111 ms	17468 KB	Output is correct
35	Correct	133 ms	17520 KB	Output is correct
36	Correct	125 ms	17740 KB	Output is correct
37	Runtime error	580 ms	112860 KB	Execution killed with signal 11
38	Execution timed out	1018 ms	19916 KB	Time limit exceeded
39	Incorrect	195 ms	18948 KB	Output isn't correct
40	Incorrect	205 ms	20524 KB	Output isn't correct
41	Correct	111 ms	17516 KB	Output is correct
42	Correct	104 ms	17512 KB	Output is correct
43	Correct	102 ms	17524 KB	Output is correct
44	Correct	126 ms	17276 KB	Output is correct
45	Correct	570 ms	52380 KB	Output is correct
46	Execution timed out	1082 ms	19712 KB	Time limit exceeded
47	Incorrect	218 ms	20672 KB	Output isn't correct
48	Incorrect	185 ms	22984 KB	Output isn't correct
49	Correct	125 ms	16896 KB	Output is correct
50	Correct	130 ms	17532 KB	Output is correct
51	Correct	162 ms	17596 KB	Output is correct
52	Correct	111 ms	17256 KB	Output is correct
53	Correct	559 ms	53540 KB	Output is correct
54	Execution timed out	1096 ms	19428 KB	Time limit exceeded