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 <vector>
#include <queue>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
const int mx = 100'000;
const int emx = 500'000;
vl c(1+mx);
vector<pii> edge[1+mx];
vi deg(1+mx, 0);
vi visit(1+emx, 0);
vector<ll> ans(1+emx);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
for(int i = 1; i <= N; i++) cin >> c[i];
for(int j = 1; j <= M; j++)
{
int u, v;
cin >> u >> v;
edge[u].push_back({v, j});
edge[v].push_back({u, j});
deg[u]++;
deg[v]++;
}
if(M > N)
{
cout << "0\n";
return 0;
}
queue<int> tbv;
for(int i = 1; i <= N; i++)
{
if(deg[i] == 1)
{
tbv.push(i);
}
}
int endv = -1;
while(!tbv.empty())
{
int u = tbv.front();
tbv.pop();
// cerr << "u = " << u << '\n';
int elim = 0;
for(auto ed: edge[u])
{
int v = ed.first;
if(visit[ed.second]) continue;
visit[ed.second] = 1;
deg[v]--;
elim = 1;
if(deg[v] <= 1)
{
tbv.push(v);
}
ans[ed.second] = 2*c[u];
cerr << ed.first << ' ' << ed.second << " : " << 2*c[u] << '\n';
c[v] -= c[u];
c[u] -= c[u];
}
if(!elim)
{
if(M == N-1)
{
if(c[u] != 0)
{
cout << "0\n";
return 0;
}
}
}
}
for(int e = 1; e <= M; e++)
{
cout << ans[e] << '\n';
}
}
Compilation message (stderr)
pipes.cpp: In function 'int main()':
pipes.cpp:59:6: warning: unused variable 'endv' [-Wunused-variable]
59 | int endv = -1;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |