Submission #747554

#	Time	Username	Problem	Language	Result	Execution time	Memory
747554		irmuun	Pipes (BOI13_pipes)	C++17	74.07 / 100	256 ms	40012 KiB

pipes

#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    if(m>n){
        cout<<0;
        return 0;
    }
    map<pair<ll,ll>,ll>mp;
    set<ll>s[n+5];
    ll c[n+5],p[n+5];
    fill(p,p+n+1,0);
    for(ll i=1;i<=n;i++){
        cin>>c[i];
    }
    vector<pair<ll,ll>>edge;
    for(ll i=1;i<=m;i++){
        ll u,v;
        cin>>u>>v;
        edge.pb({u,v});
        s[u].insert(v);
        s[v].insert(u);
        p[u]++;
        p[v]++;
    }
    if(m==n-1){
        queue<ll>q;
        for(ll i=1;i<=n;i++){
            if(p[i]==1){
                q.push(i);
            }
        }
        for(ll i=1;i<n;i++){
            ll x=q.front();
            q.pop();
            if(p[x]==0){
                continue;
            }
            ll y=*s[x].begin();
            mp[{x,y}]=2*c[x];
            c[y]-=c[x];
            p[y]--;
            p[x]--;
            s[x].erase(y);
            s[y].erase(x);
            if(p[y]==1){
                q.push(y);
            }
        }
        if(c[q.front()]!=0){
            cout<<0;
            return 0;
        }
        for(auto [u,v]:edge){
            cout<<mp[{u,v}]+mp[{v,u}]<<"\n";
        }
    }
    else{
        queue<ll>q;
        ll used[n+5];
        fill(used,used+n+1,0);
        for(ll i=1;i<=n;i++){
            if(p[i]==1){
                q.push(i);
            }
        }
        ll cnt=n;
        while(!q.empty()){
            ll x=q.front();
            q.pop();
            if(used[x]==1){
                continue;
            }
            used[x]=1;
            cnt--;
            ll y=*s[x].begin();
            mp[{x,y}]=2*c[x];
            c[y]-=c[x];
            p[y]--;
            p[x]--;
            s[x].erase(y);
            s[y].erase(x);
            if(p[y]==1){
                q.push(y);
            }
        }
        if(cnt%2==0){
            cout<<0;
            return 0;
        }
        vector<ll>node;
        ll sum=0;
        function <void(ll)> dfs=[&](ll x){
            used[x]=1;
            node.pb(x);
            sum+=c[x];
            for(auto y:s[x]){
                if(used[y]==0){
                    dfs(y);
                }
            }
        };
        for(ll i=1;i<=n;i++){
            if(used[i]==0){
                dfs(i);
                break;
            }
        }
        sum/=2;
        ll sz=node.size();
        node.insert(node.end(),all(node));
        ll a[sz*2+5];
        a[0]=c[node[0]];
        a[1]=c[node[1]];
        for(ll i=2;i<sz*2;i++){
            a[i]=a[i-2]+c[node[i]];
        }
        for(ll i=0;i<sz;i++){
            mp[{node[i],node[i+1]}]=sum-(a[i+(sz-1)]-a[i]);
        }
        for(auto [u,v]:edge){
            cout<<mp[{u,v}]+mp[{v,u}]<<"\n";
        }
    }
}

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