Submission #731783

#	Time	Username	Problem	Language	Result	Execution time	Memory
731783		n0sk1ll	Pipes (BOI13_pipes)	C++17	100 / 100	166 ms	19872 KiB

pipes

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

int c[100005];
graph g(100005);
int deg[100005];
bool vis[100005];

map<pii,int> eds;
int ans[100005];

li tsum=0;
vector<int> kako;
void dfs(int p, int mf)
{
    if (vis[p]) return; vis[p]=1,tsum+=mf*c[p],kako.pb(p);
    for (auto it : g[p]) dfs(it,-mf);
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    if (m>n) return cout<<0,0;

    fff(i,1,n) cin>>c[i];
    fff(i,1,m)
    {
        int u,v; cin>>u>>v;
        g[u].pb(v),g[v].pb(u);
        deg[u]++,deg[v]++;
        eds[{min(u,v),max(u,v)}]=i;
    }

    queue<int> bfs;
    fff(i,1,n) if (deg[i]<=1) bfs.push(i);

    int kolko=0;
    while (!bfs.empty())
    {
        int p=bfs.front(); bfs.pop();
        if (vis[p]) continue;
        vis[p]=true;

        for (auto it : g[p]) if (!vis[it])
        {
            ans[eds[{min(p,it),max(p,it)}]]=c[p];
            c[it]-=c[p],c[p]=0;

            deg[it]--,deg[p]--;
            if (deg[it]<=1) bfs.push(it);
            kolko++;
        }
    }

    if (m==kolko)
    {
        fff(i,1,n) if (c[i]) return cout<<0,0;
        fff(i,1,m) cout<<2*ans[i]<<"\n";
        return 0;
    }

    if ((m-kolko)%2==0) return cout<<0,0;

    fff(i,1,n) if (c[i])
    {
        dfs(i,1);
        if (tsum%2==1) return cout<<0,0;

        li x=tsum/2;
        ff(i,0,(int)kako.size())
        {
            int p=kako[i],q=kako[(i+1)%((int)kako.size())];
            x=c[p]-x;
            ans[eds[{min(p,q),max(p,q)}]]=x;
        }

        fff(i,1,m) cout<<2*ans[i]<<"\n";
        return 0;
    }

    fff(i,1,m) cout<<2*ans[i]<<"\n";
}

//Note to self: Check for overflow

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:49:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |     if (vis[p]) return; vis[p]=1,tsum+=mf*c[p],kako.pb(p);
      |     ^~
pipes.cpp:49:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |     if (vis[p]) return; vis[p]=1,tsum+=mf*c[p],kako.pb(p);
      |                         ^~~

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