Submission #83630

#	Time	Username	Problem	Language	Result	Execution time	Memory
83630		Bodo171	Pipes (BOI13_pipes)	C++14	100 / 100	112 ms	13884 KiB

pipes

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
vector< pair<int,int> > v[nmax];
pair<int,int> cyc[nmax];
int rep[nmax],wh[nmax],mu[nmax],viz[nmax];
long long am[nmax],ans[nmax],vreau[nmax];
long long act;
int n,nr,m,i,j,sz,x,y,a,b;
void solve(int x)
{
    int nod=0;
    viz[x]=1;
    for(int i=0;i<v[x].size();i++)
        if(!viz[v[x][i].first])
    {
        nod=v[x][i].first;
        solve(nod);
        ans[v[x][i].second]=vreau[nod]-am[nod];
        am[x]+=(vreau[nod]-am[nod]);
    }
}
int it=0;
bool gasit;
void dfs(int x)
{
    rep[++nr]=x;wh[x]=nr;
    for(int i=0;i<v[x].size()&&(!gasit);i++)
    {
        mu[nr]=v[x][i].second;
        if(!wh[v[x][i].first])
        {
            dfs(v[x][i].first);
        }
        else
        {
            if(wh[v[x][i].first]<nr-1)
            {
                gasit=1;
                for(j=wh[v[x][i].first];j<=nr;j++)
                {
                    cyc[++sz]={rep[j],mu[j]};
                }
            }
        }
    }
    nr--;
}
void gaseste_ciclu()
{
    dfs(1);
    for(i=1;i<=sz;i++)
        viz[cyc[i].first]=1;
    if(!(sz%2))
    {
        cout<<"0";
        return;
    }
    for(i=1;i<=sz;i++)
    {
        x=cyc[i].first;
        solve(x);
        vreau[x]-=am[x];
    }
    for(i=1;i<=sz;i++)
    {
        x=cyc[i].first;
        if((i&1)) act+=vreau[x];
        else act-=vreau[x];
    }
    if(act%2)
    {
        cout<<"0";
        return;
    }
    ans[cyc[sz].second]=act/2;
    cyc[0]=cyc[sz];
    for(i=1;i<sz;i++)
    {
        ans[cyc[i].second]=vreau[cyc[i].first]-ans[cyc[i-1].second];
    }
    for(i=1;i<=m;i++)
        cout<<2*ans[i]<<'\n';
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    if(m>n)
    {
        cout<<"0";
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        cin>>vreau[i];
    }
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
    }
    if(m==n-1)
    {
        solve(1);
        if(1LL*vreau[1]-am[1])
        {
            cout<<"0";
            return 0;
        }
        for(i=1;i<=m;i++)
            cout<<2*ans[i]<<'\n';
    }
    else
    {
        gaseste_ciclu();
    }
    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void solve(int)':
pipes.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
pipes.cpp: In function 'void dfs(int)':
pipes.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size()&&(!gasit);i++)
                 ~^~~~~~~~~~~~

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