제출 #489863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489863		SirCovidThe19th	Pipes (BOI13_pipes)	C++17	70.19 / 100	448 ms	106720 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 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 / 30
• Subtask 2: 40.18518518518518 / 70