Submission #742018

#	Time	Username	Problem	Language	Result	Execution time	Memory
742018		irmuun	Pipes (BOI13_pipes)	C++17	74.07 / 100	254 ms	21664 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-1){
        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]++;
    }
    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";
    }
}

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