Submission #253386

#	Time	Username	Problem	Language	Result	Execution time	Memory
253386		m3r8	Pipes (BOI13_pipes)	C++14	100 / 100	231 ms	17336 KiB

pipes

#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
#include <functional>

#define N 100100
#define M 500500
#define ii std::pair<int,int>
#define ll long long

std::vector<ii> adj[N];

ll val[M];
int iq[N];
int used[M];
ll cn[N];
int dg[N];
std::queue<int> que;
std::vector<int> rm;

ll dfs(int v, int p, int cc, int en){
  if(v == en)return 0ll;
  ll erg = 0;  
  if(cc)erg += cn[v]*2ll;
  for(auto i: adj[v]){
    if(i.second != p && !iq[i.second]){
      erg += dfs(i.second,v,cc^1,en);
    };  
  };
  return erg;
};

int main(void){
  int n,m;  
  int a,b;
  scanf("%d %d",&n,&m);
  for(int i = 1;i<=n;i++){
    scanf("%lld",&cn[i]);  
  };
  for(int i = 0;i<m;i++){
    scanf("%d %d",&a,&b);  
    adj[a].push_back({i,b});
    adj[b].push_back({i,a});
  };
  int pos = 1;
  if(m > n){
    pos = 0;
  }else{
    for(int i = 1;i<=n;i++){
      dg[i] = adj[i].size();
      if(adj[i].size() == 1){
        iq[i] = 1;
        que.push(i);  
      };
    };  
    while(que.size()){
      int akt = que.front();que.pop();  
      for(auto i : adj[akt]){
        if(!used[i.first]){
          val[i.first] = cn[akt];
          used[i.first] = 1;
          dg[i.second]--;
          cn[i.second] -= val[i.first];
          if(dg[i.second] == 1){
            que.push(i.second);  
            iq[i.second] = 1;
          };
        };  
      };
    };
    ll sm = 0;
    for(int i = 1;i<=n;i++){
      if(!iq[i]){
        sm += cn[i];
        rm.push_back(i); 
      };  
    };
    if(rm.size()%2 == 0 && rm.size()){
      pos = 0;
    }else if(rm.size()){
      int st = rm[0];
      int en = 0;
      int idd;
      for(auto i: adj[st]){
        if(!iq[i.second]){
          en = i.second;
          idd = i.first;
          break;
        };  
      };
      ll tmp = dfs(st,en,0,en);
      sm -= tmp;
      val[idd] = sm/2ll;
      used[idd] = 1;
      dg[st]--;
      dg[en]--;
      cn[st] -= val[idd];
      cn[en] -= val[idd];
      que.push(st);
      que.push(en);
      iq[st] = 1;
      iq[en] = 1;
      while(que.size()){
        int akt = que.front();que.pop();  
        for(auto i: adj[akt]){
          if(!used[i.first]){
            val[i.first] = cn[akt];
            used[i.first] = 1;
            dg[i.second]--;
            cn[i.second] -= val[i.first];
            if(dg[i.second] == 1){
              que.push(i.second);  
              iq[i.second] = 1;
            };
          }; 
        };
      };
    };
  };
  if(pos){
    for(int i = 0;i<m;i++){
      printf("%lld\n",val[i] * 2ll);  
    };
  }else{
    printf("0\n");  
  };
  return 0;
};

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&cn[i]);  
     ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);  
     ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:95:17: warning: 'idd' may be used uninitialized in this function [-Wmaybe-uninitialized]
       used[idd] = 1;
       ~~~~~~~~~~^~~

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