#include <bits/stdc++.h>
using namespace std;
#define SZ(s) (int)s.size()
int n, m, nd;
map <pair<int,int>,int> ans;
vector <int> a, u1, u2, deg, vis, v1;
vector <vector <int>> v;
void dfs(int x){
vis[x] = true;
v1.push_back(x);
for(auto i : v[x]){
if(deg[i] == 2 and !vis[i]){
dfs(i);
return;
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
a.resize(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
v.resize(n+1), deg.resize(n+1,0);
u1.resize(m+1), u2.resize(m+1);
for(int i = 1; i <= m; i++){
cin >> u1[i] >> u2[i];
v[u1[i]].push_back(u2[i]);
v[u2[i]].push_back(u1[i]);
}
if(m > n){
cout << 0;
return 0;
}
queue <int> q;
for(int i = 1; i <= n; i++){
deg[i] = SZ(v[i]);
if(deg[i] == 1){
q.push(i);
}
}
while(!q.empty()){
int ind = q.front();
q.pop();
deg[ind]--;
for(auto i : v[ind]){
if(deg[i] > 0){
deg[i]--;
ans[{min(i,ind), max(i,ind)}] = a[ind];
a[i] -= a[ind];
if(deg[i] == 1) q.push(i);
}
}
}
if(n == m+1){
for(int i = 1; i <= m; i++){
cout << 2*ans[{min(u1[i], u2[i]), max(u1[i], u2[i])}] << '\n';
}
return 0;
}
vis.assign(n+1, 0);
for(int i = 1; i <= n; i++){
if(deg[i] == 2){
nd = i;
break;
}
}
dfs(nd);
int n1 = SZ(v1);
if(n1 % 2 == 0){
cout << 0;
return 0;
}
int s = 0;
for(int i = 1; i < n1; i++){
s *= (-1);
s += a[v1[i-1]];
ans[{min(v1[i-1], v1[i]), max(v1[i-1], v1[i])}] = s;
}
s *= (-1);
s += (a[v1[n1-1]]);
s -= a[v1[0]];
ans[{min(v1[n1-1], v1[1]), max(v1[n1-1], v1[1])}] = s;
for(int i = 1; i <= m; i++){
cout << 2*ans[{min(u1[i], u2[i]), max(u1[i], u2[i])}] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |