Submission #230467

#	Time	Username	Problem	Language	Result	Execution time	Memory
230467		mehrdad_sohrabi	Pipes (BOI13_pipes)	C++14	100 / 100	293 ms	35428 KiB

pipes

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
vector <int> g[N];
ll hi[N];
ll ans[N];
map <pii,int> mp;
ll val[N],par[N],vis[N];
ll ras1=0,ras2=0;
ll dfsd(ll v,ll p,ll h){
   // cout << v << " " << p << " " << h << endl;
    par[v]=p;
    hi[v]=h;
    for (auto u : g[v]){
        if (u==p) continue;
        if (hi[u]<hi[v] && hi[u]!=0){
            ras1=v,ras2=u;
        //    cout << v << " " << u << endl;
            continue;
        }
        if (hi[u]!=0) continue;
        dfsd(u,v,h+1);
    }
}
ll dfs(ll v,ll p){
    for (auto u : g[v]){
        if (u==p || vis[u]) continue;
        dfs(u,v);
        val[v]+=-val[u];
        mp[{u,v}]=2*-val[u];
        mp[{v,u}]=mp[{u,v}];
        val[u]=0;
    }
}
vector <pii> yal;
int32_t main(){
    sync;
    ll n,m;
    cin >> n >> m;
    if (m>n) kill(0);
    for (int i=1;i<=n;i++){
        cin >> val[i];
        val[i]=-val[i];
    }
    for (int i=0;i<m;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        yal.pb({u,v});
    }
    if (m>n) kill(0);
    if (m==n-1){
        dfs(1,1);
        if (val[1]!=0) kill(0);
    }
    if (m==n){
        dfsd(1,1,1);
        vector <int> ras;

        while(ras1!=ras2){
            ras.pb(ras1);
            vis[ras1]=1;
            ras1=par[ras1];
        }
        ras.pb(ras2);
        vis[ras2]=1;
        for (int i=1;i<=n;i++){
            if (vis[i]){
                dfs(i,i);
            }
        }
        ll t=ras.size();
        if (t%2==0) kill(0);
        for (int i=1;i<t;i++){
            ll v=ras[i],u=ras[(i+1)%t];
            val[u]+=-val[v];
            mp[{u,v}]=2*-val[v];
            mp[{v,u}]=2*-val[v];
            val[v]=0;

        }
        ll o=val[ras[0]];
        if (o%2!=0) kill(0);
        o/=2;
        o=-o;
        for (int i=0;i<t;i++){
            ll v=ras[i],u=ras[(i+1)%t];
            if (i%2==0){
                mp[{u,v}]+=2*o;
                mp[{v,u}]+=2*o;
            }
            else{
                mp[{u,v}]-=2*o;
                mp[{v,u}]-=2*o;
            }
        }
    }
    for (pii v : yal){
        cout << mp[v] << endl;
    }
}

Compilation message (stderr)

pipes.cpp: In function 'll dfsd(ll, ll, ll)':
pipes.cpp:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
pipes.cpp: In function 'll dfs(ll, ll)':
pipes.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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