Submission #267160

#	Time	Username	Problem	Language	Result	Execution time	Memory
267160		shrek12357	Pipes (BOI13_pipes)	C++14	100 / 100	307 ms	35320 KiB

pipes

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#include<stack>
#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],deg[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];
    }
 
    val[edge] = ar[cur];
 
    return;
}
 
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
    {
        ll nodes = n;
        stack < pi > s;
 
        rep(i,1,n+1)
        {
            deg[i] = graph[i].size();
 
            if(deg[i] == 1)
            {
                vis[i] = true;
                s.push(mp(i,graph[i][0].second));
            }
        }
 
        while(!s.empty())
        {
            nodes--;
            ll cur = s.top().first;
            ll e = s.top().second;
            s.pop();
            deg[cur]--;
 
          //  cout << cur << " " << e << endl;
            val[e] = ar[cur];
 
       //     cout << deg[1] <<endl;
 
            rep(i,0,graph[cur].size())
            {
                ll v = graph[cur][i].first;
 
                if(deg[v] <= 1)
                    continue;
 
                ar[v] -= val[e];
 
                deg[v]--;
                graph[v].erase(find(graph[v].begin(),graph[v].end(),mp(cur,graph[cur][i].second)));
 
             //   cout << v << " " << deg[v] << endl;
 
                if(deg[v] == 1)
                {
                    vis[v] = true;
                    s.push(mp(v,graph[v][0].second));
                }
            }
        }
 
        ll st = 1;
 
        while(vis[st])
        {
            st++;
        }
 
        ll start = st;
 
        while(!vis[start])
        {
            pi potential;
            bool found = false;
            rep(i,0,graph[st].size())
            {
                ll v =  graph[st][i].first;
 
                if(!vis[v])
                {
                    if(v == start)
                    {
                        potential = mp(st,graph[st][i].second);
                        continue;
                    }
 
                    found = true;
                    neo.push_back(mp(st,graph[st][i].second));
                    vis[v] = true;
                    st = v;
                    break;
                }
            }
 
            if(!found)
            {
                vis[start] = true;
                neo.push_back(potential);
                st = start;
            }
        }
 
        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] =ar[neo[i].first]  - val[neo[i-1].second];
            }
 
            rep(i,0,m)
            {
                cout << 2*val[i] << endl;
            }
        }
    }
 
    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void solvetree(long long int, long long int, long long int)':
pipes.cpp:14:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
   27 |     rep(i,0,graph[cur].size())
      |         ~~~~~~~~~~~~~~~~~~~~~       
pipes.cpp:27:5: note: in expansion of macro 'rep'
   27 |     rep(i,0,graph[cur].size())
      |     ^~~
pipes.cpp: In function 'int main()':
pipes.cpp:14:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
  106 |             rep(i,0,graph[cur].size())
      |                 ~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:106:13: note: in expansion of macro 'rep'
  106 |             rep(i,0,graph[cur].size())
      |             ^~~
pipes.cpp:14:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
  141 |             rep(i,0,graph[st].size())
      |                 ~~~~~~~~~~~~~~~~~~~~
pipes.cpp:141:13: note: in expansion of macro 'rep'
  141 |             rep(i,0,graph[st].size())
      |             ^~~
pipes.cpp:14:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
  177 |             rep(i,0,neo.size())
      |                 ~~~~~~~~~~~~~~      
pipes.cpp:177:13: note: in expansion of macro 'rep'
  177 |             rep(i,0,neo.size())
      |             ^~~
pipes.cpp:14:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i,a,b) for(int i = a;i < b;i++)
......
  185 |             rep(i,1,neo.size()-1)
      |                 ~~~~~~~~~~~~~~~~    
pipes.cpp:185:13: note: in expansion of macro 'rep'
  185 |             rep(i,1,neo.size()-1)
      |             ^~~

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