Submission #1149204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149204		spycoderyt	Pipes (BOI13_pipes)	C++20	100 / 100	386 ms	81112 KiB

pipes

#include <bits/stdc++.h>
#define int long long 
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 5e5+5;
set<int> A[N];
pii e[N];
int c[N],ans[N],deg[N];
int n,m,a,b;
int get_node(int u,int i) {
    int adj_edge = (i == 0?*A[u].begin() : *A[u].rbegin());
    int adj_node = e[adj_edge].f ^ e[adj_edge].s ^ u;
    return adj_node;
}
void dfs(int u,int p, int root,vector<pii> &order) {
    int nxt;
    nxt = get_node(u,0);
    if(nxt!=p){
        order.push_back({u,*A[u].begin()});
    } else {
        nxt = get_node(u,1);
        if(nxt!=p)order.push_back({u,*A[u].rbegin()});
    }
    if(nxt!=root)dfs(nxt,u,root,order);
}
int32_t main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>c[i];
    for(int i = 1;i<=m;i++) {
        cin>>a>>b;
        A[a].insert(i);
        A[b].insert(i);
        deg[a]++,deg[b]++;
        e[i] = {a,b};
    }    
    queue<int> q;
    for(int i = 1;i<=n;i++) q.push(i);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        if(A[cur].size() == 1) {
            int adj_edge = *A[cur].begin();
            int adj_node = (e[adj_edge].f==cur?e[adj_edge].s : e[adj_edge].f);
            ans[adj_edge] = 2LL * c[cur];
            c[cur] -= ans[adj_edge]/2LL;
            c[adj_node] -= ans[adj_edge]/2LL;
            A[cur].erase(adj_edge);
            A[adj_node].erase(adj_edge);
            if(A[adj_node].size() == 1) q.push(adj_node);
        }
    }
    //check for more than 3 or odd cycle
    int cnt = 0;
    for(int i = 1;i<=n;i++) {
        if(A[i].size() > 2) {
            cout << "0\n";
            return 0;
        }
        cnt += A[i].size() == 2;
    }
    if(cnt > 0 && cnt % 2 == 0) {
            cout << "0\n";

        return 0;
    }
    int st = 0;
    for(st = 1;st<=n;st++){
        if(A[st].size()==2){
            break;
        }
    }
    if(st<=n) {
        vector<pii> order;
        dfs(st, -1, st, order);
        int sus = 2LL * c[st];
        int diff = 0;
        for(int i = 1;i<order.size();i++) {
            diff = 2LL * c[order[i].f] - diff;
        }
        ans[order[0].s] = (sus - diff) / 2LL;
        for(int i = 1;i<order.size();i++) ans[order[i].s] = 2LL * c[order[i].f] - ans[order[i-1].s];
    }
    for(int i = 1;i<=m;i++)cout<<ans[i]<<"\n";

}

/*
one edge = uniquely determines the edge weight
cycles can be unique if there are no arbitrary in/outflows
check for unique determination of weights
then check for cycle and cycle validity

1) check  for unique determinants and propagate them
2) check for cycle

so many tricks
- check for double odd cycle using deg >= 3
- insert edge id and not pair
- set instead of vec

*/

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