Submission #633107

#	Time	Username	Problem	Language	Result	Execution time	Memory
633107		anhduc2701	Pipes (BOI13_pipes)	C++17	93.52 / 100	137 ms	18488 KiB

pipes

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100005],par[100005],H[100005],ans[100005];
bool vis[100005];
long long c[2];
vector<pair<int,int>>Edge;
vector<pair<int,int>>G[100005];
void DFS(int u,int p=-1){
    for(auto v:G[u]){
        if(v.first==p)continue;
        if(H[v.first]!=-1){
            if((H[u]-H[v.first])%2==1){
                cout<<0;
                exit(0);
            }
        }
        else{
            H[v.first]=H[u]+1;
            DFS(v.first,u);
        }
    }
}
void DFS2(int u,int p=-1){
    vis[u]=1;
    for(auto v:G[u]){
        if(vis[v.first])continue;
        DFS2(v.first,u);
        ans[v.second]=a[v.first];
        a[u]-=a[v.first];
    }
}
int main(){
    cin>>n>>m;
    if(n<m){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++){
        H[i]=-1;
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back({v,i-1});
        G[v].push_back({u,i-1});
        Edge.push_back({u,v});
    }
    H[1]=0;
    DFS(1);
    for(int i=1;i<=n;i++){
        c[H[i]%2]+=a[i];
    }
    for(int i=0;i<m;i++){
        pair<int,int>x=Edge[i];
        if(H[x.first]%2==H[x.second]%2){
            if(H[x.first]%2==1){
                ans[i]=(c[i]-c[0])/2;
                a[x.first]-=ans[i];
                a[x.second]-=ans[i];
            }
            else{
                ans[i]=(c[0]-c[1])/2;
                a[x.first]-=ans[i];
                a[x.second]-=ans[i];
            }
        }
    }
    DFS2(1);
    for(int i=0;i<m;i++){
        cout<<ans[i]*2<<'\n';
    }
}
// 0->1 ->2 ->3 ->4 ->5->6->2

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