Submission #78685

#	Time	Username	Problem	Language	Result	Execution time	Memory
78685		Charis02	Pipes (BOI13_pipes)	C++14	88.33 / 100	270 ms	29428 KiB

pipes

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e9+7

using namespace std;

ll n,m,ar[N],val[N];
bool vis[N],cycle;
vector < vector < pi > > graph(N);
vector < pi > neo;

void solvetree(ll cur,ll par,ll edge)
{
    rep(i,0,graph[cur].size())
    {
        ll v = graph[cur][i].first;

        if(v == par)
            continue;

        solvetree(v,cur,graph[cur][i].second);

        ar[cur] -= val[graph[cur][i].second];
    }

//    cout << cur << " " << par << " " << edge << " " << ar[cur] <<endl;

    val[edge] = ar[cur];

    return;
}

bool solvemn(ll cur,ll par,ll edge)
{
    if(vis[cur])
    {
        if(!cycle)
            neo.push_back(mp(cur,edge));

        cycle = true;
        return true;
    }

    bool found= false;
    vis[cur] = true;

    rep(i,0,graph[cur].size())
    {
        ll v = graph[cur][i].first;

        if(v == par)
            continue;

        if(solvemn(v,cur,graph[cur][i].second))
        {
            if(!neo.empty() && cur == neo[0].first)
                continue;

            neo.push_back(mp(cur,edge));
            found = true;
        }
        else
            ar[cur] -= val[graph[cur][i].second];
    }

    if(!found)
        val[edge] = ar[cur];

    return found;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> m;

    rep(i,1,n+1)
    {
        cin >> ar[i];
    }

    rep(i,0,m)
    {
        ll a,b;
        cin >> a >> b;
        graph[a].push_back(mp(b,i));
        graph[b].push_back(mp(a,i));
    }

    if(m > n)
    {
        cout << 0 << endl;
        return 0;
    }
    else if(m == n-1)
    {
        solvetree(1,1,m);

        rep(i,0,m)
        {
            cout << 2*val[i] << endl;
        }
    }
    else
    {
        solvemn(1,1,m);

        if((neo.size())%2==0)
        {
            cout << 0 << endl;
        }
        else
        {
            ll s = 0;

            rep(i,0,neo.size())
            {
                s += ar[neo[i].first]*pow(-1,i%2);
            }

            val[neo[neo.size()-1].second] = s/2;
            val[neo[0].second] = ar[neo[0].first] - s/2;

            rep(i,1,neo.size()-1)
            {
                val[neo[i].second] = -val[neo[i-1].second] + ar[neo[i].first];
            }

            rep(i,0,m)
            {
                cout << 2*val[i] << endl;
            }
        }
    }

    return 0;
}

/*
3 3
1 3 2
1 2
1 3
2 3
*/

Compilation message (stderr)

pipes.cpp: In function 'void solvetree(long long int, long long int, long long int)':
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:26:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
pipes.cpp:26:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
pipes.cpp: In function 'bool solvemn(long long int, long long int, long long int)':
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:59:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
pipes.cpp:59:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
pipes.cpp: In function 'int main()':
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:129:17:
             rep(i,0,neo.size())
                 ~~~~~~~~~~~~~~      
pipes.cpp:129:13: note: in expansion of macro 'rep'
             rep(i,0,neo.size())
             ^~~
pipes.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
pipes.cpp:137:17:
             rep(i,1,neo.size()-1)
                 ~~~~~~~~~~~~~~~~    
pipes.cpp:137:13: note: in expansion of macro 'rep'
             rep(i,1,neo.size()-1)
             ^~~

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