This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Unknown's C++ Template (v3.2)
*/
#include "bits/stdc++.h"
using namespace std;
#define int long long
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second
#ifdef LOCAL
#define debug(x) cout << #x << " = " << x << "\n";
#else
#define debug(x) ;
#endif
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }
template <class T>
ostream& operator << (ostream& out, vector<T> x){
out << "[";
for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
out << "]"; return out;
}
template <class T>
istream& operator >> (istream& in, vector<T> &x){
for (auto &i: x) in >> i;
return in;
}
const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 2e5 + 64;
const ll inf = 1e18;
const ld eps = 1e-6;
const int multitest = 0;
int n, m, root = -1;
vi deg, change, res;
vi pt_order, edge_order;
vii edges;
vvii adj;
void dfs(int x, int p = -1){
if (x == root && p >= 0) return;
pt_order.pb(x);
for (auto k: adj[x]){
if (k.fi == p) continue;
if (!deg[k.fi]) continue;
edge_order.pb(k.se);
dfs(k.fi, x);
break;
}
}
void main_program(){
cin >> n >> m;
deg.assign(n, 0); change.resize(n); cin >> change;
adj.resize(n);
res.resize(m); edges.resize(m);
for (int i = 0; i < m; i++){
int x, y; cin >> x >> y;
x--; y--;
deg[x]++; deg[y]++;
edges[i] = {x, y};
adj[x].pb({y, i}); adj[y].pb({x, i});
}
queue<int> q;
for (int i = 0; i < n; i++){
if (deg[i] == 1) q.push(i);
}
while (!q.empty()){
int x = q.front(); q.pop();
for (auto k: adj[x]){
if (deg[k.fi]){
res[k.se] += change[x] * 2;
change[k.fi] -= change[x];
deg[k.fi]--;
if (deg[k.fi] == 1) q.push(k.fi);
}
}
change[x] = 0;
if (deg[x]) deg[x]--;
}
if (((n == m) && (*max_element(all(deg)) == 2)) || (*max_element(all(deg)) == 0)){
for (int i = 0; i < n; i++){
if (deg[i]) root = i;
}
if (root >= 0){
dfs(root);
int tt = 0;
for (auto i: pt_order) tt += change[i];
for (int i = 1; i < sz(pt_order); i += 2) tt -= change[pt_order[i]] * 2;
res[edge_order.back()] = tt;
for (int i = sz(pt_order) - 1; i >= 1; i--){
res[edge_order[i-1]] = 2 * change[pt_order[i]] - res[edge_order[i]];
}
}
for (int i = 0; i < m; i++) cout << res[i] << "\n";
}
else cout << "0\n";
}
void pre_main(){
}
signed main(){
#ifdef LOCAL
auto stime = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
if (fopen(".inp", "r")){
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
#endif
int t = 1; if (multitest) cin >> t;
pre_main();
while (t--) main_program();
#ifdef LOCAL
auto etime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
cout << "\n[" << duration << "ms]\n";
#endif
}
Compilation message (stderr)
pipes.cpp: In function 'int main()':
pipes.cpp:147:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | freopen(".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
pipes.cpp:148:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen(".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |