Submission #58596

#	Time	Username	Problem	Language	Result	Execution time	Memory
58596		Batrr	Pipes (BOI13_pipes)	C++14	74.07 / 100	444 ms	51032 KiB

pipes

#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=5e5+123,inf=1e18,mod=1e9+7,N=360360,LOG=20;
vector< pair<int,int> >g[maxn],G[maxn],path;
ll n,m,cnt[maxn],ans[maxn],a[maxn],mm;
bitset<maxn>used;
void dfs(int v,int st){
    used[v]=1;
    for(int i=0;i<G[v].size();i++){
        int to=G[v][i].f;
        if(to==st)
            path.pb(G[v][i]);
        if(!used[to]){
            path.pb(G[v][i]);
            dfs(to,st);
        }
    }
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif                                     
    IOS
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        int v,u;
        cin>>v>>u; 
        g[v].pb({u,i});
        g[u].pb({v,i});
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        cnt[i]=g[i].size();
        if(cnt[i]==1)
            q.push(i);
    }
    while(!q.empty()){
        int v=q.front();
        q.pop();
        used[v]=1;
        for(auto to:g[v])
            if(!used[to.f]){
                cnt[to.f]--;
                if(cnt[to.f]==1)
                    q.push(to.f);
                ans[to.s]=a[v]*2;
                a[to.f]-=a[v];
            }
    }
    mm=0;
    for(int v=1;v<=n;v++){
        if(used[v])
            continue;
        for(auto to:g[v])
            if(!used[to.f]){
                mm++;
                G[v].pb(to);
            }
            
    }
    for(int i=1;i<=n;i++)
        if(!used[i] && G[i].size()!=2)
            m=-1;
    if( n==used.count()){
        for(int i=1;i<=m;i++)
            cout<<ans[i]<<endl;
        return 0;
    }
    if( (n-used.count())%2==0 || mm!=n-used.count())
        cout<<0,exit(0);
    for(int i=1;i<=n;i++)
        if(!used[i]){
            dfs(i,i);
            if( (n-used.count())!=0 )
                cout<<0,exit(0);
            ll x=0;
            for(int i=0;i<path.size();i++){
                if(i%2==0)          
                    x+=a[path[i].f];
                else
                    x-=a[path[i].f];    
            }                           
            a[path[path.size()-1].f]-=x;
            a[path[0].f]-=x;
            for(int i=1;i<path.size();i++){
                a[path[i].f]-=a[path[i-1].f];
                a[path[i-1].f]-=a[path[i-1].f];
            }
            for(int i=1;i<=m;i++)
                cout<<ans[i]<<endl;
            break;
        }
        
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[v].size();i++){
                 ~^~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:79:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( n==used.count()){
         ~^~~~~~~~~~~~~~
pipes.cpp:84:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( (n-used.count())%2==0 || mm!=n-used.count())
                                  ~~^~~~~~~~~~~~~~~~
pipes.cpp:92:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<path.size();i++){
                         ~^~~~~~~~~~~~
pipes.cpp:100:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=1;i<path.size();i++){
                         ~^~~~~~~~~~~~

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