Submission #489907

#	Time	Username	Problem	Language	Result	Execution time	Memory
489907		SirCovidThe19th	Pipes (BOI13_pipes)	C++17	100 / 100	399 ms	54872 KiB

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 mN = 1e5 + 5, mM = 5e5 + 5;

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

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] * 2; 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];
    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 (cnt){
		dfs(st, 0);
        
        pii rem = *prev(adj[st].end()); 
        A[st] -= altSm / 2; A[rem.f] -= altSm / 2;
        ans[rem.s] = altSm;
        adj[st].erase(rem); adj[rem.f].erase({st, rem.s});
        
        compressLeaves();
	}
    FOR(i, 0, m) cout<<ans[i]<<"\n";
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70