This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
const int mod=1e9+7,mxn=5e5+5,lg=30,inf=1e18,minf=-1e18;
int ans[mxn+10],val[mxn+10],up[mxn+10],curval[mxn+10];
vector<pii>adj[mxn+10];
bitset<mxn+10>vis;
bool yes=false;
void solve(int cur,int p){
if(vis[cur])return void(yes=true);
vis[cur]=true;
bool leaf=true;
for(auto i:adj[cur])if(i.f!=p)leaf=false;
if(leaf){
ans[up[cur]]+=val[cur];
curval[p]+=val[cur];
return;
}
for(auto i:adj[cur]){
if(i.f==p)continue;
up[i.f]=i.s;
solve(i.f,cur);
}
if(cur==1)return;
ans[up[cur]]+=(val[cur]-curval[cur]);
curval[p]+=(val[cur]-curval[cur]);
}
vector<ppii>path;
int deg[mxn+10],sum,cnt=0;
int start=1;
void solve2(int cur,int p){
if(vis[cur])return;
cnt++;
sum+=(val[cur]-curval[cur])*((cnt%2)?1:-1);
vis[cur]=true;
for(auto i:adj[cur]){
if(i.f==start&&i.f!=p)path.pb({i.s,{i.f,cur}});
if(i.f==p||vis[i.f])continue;
up[i.f]=i.s;
path.pb({i.s,{i.f,cur}});
solve2(i.f,cur);
}
}
int32_t main(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>val[i];
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
adj[a].pb({b,i});
adj[b].pb({a,i});
}
if(m>n){
cout<<0;
return 0;
}
if(m==n-1){
solve(1,-1);
for(int i=0;i<m;i++)cout<<2*ans[i]<<'\n';
return 0;
}
stack<int>st;
for(int i=1;i<=n;i++){
if(adj[i].size()==1)st.push(i);
deg[i]=adj[i].size();
}
cnt=0;
while(!st.empty()){
vis[st.top()]=true;
for(auto i:adj[st.top()]){
if(vis[i.f])continue;
deg[i.f]--;
ans[i.s]+=val[st.top()];-curval[st.top()];
curval[i.f]+=val[st.top()];-curval[st.top()];
if(deg[i.f]==1)st.push(i.f);
}
st.pop();
cnt++;
}
for(int i=1;i<=n;i++)if(!vis[i])start=i;
if((n-cnt)%2==0){
cout<<0;
return 0;
}
cnt=0;
solve2(start,-1);
sum/=2;
reverse(all(path));
for(int i=0;i<path.size();i++){
if(i==0){
ans[path[i].f]+=sum;
curval[path[i].s.f]+=sum;
curval[path[i].s.s]+=sum;
}
else{
ans[path[i].f]+=val[path[i].s.f]-curval[path[i].s.f];
curval[path[i].s.f]+=val[path[i].s.f]-curval[path[i].s.f];
curval[path[i].s.s]+=val[path[i].s.f]-curval[path[i].s.f];
}
}
for(int i=0;i<m;i++)cout<<2*ans[i]<<'\n';
}
Compilation message (stderr)
pipes.cpp: In function 'int32_t main()':
pipes.cpp:103:37: warning: value computed is not used [-Wunused-value]
103 | ans[i.s]+=val[st.top()];-curval[st.top()];
| ^~~~~~~~~~~~~~~~~
pipes.cpp:104:40: warning: value computed is not used [-Wunused-value]
104 | curval[i.f]+=val[st.top()];-curval[st.top()];
| ^~~~~~~~~~~~~~~~~
pipes.cpp:119:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=0;i<path.size();i++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |