이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e5 + 10;
bool mark[maxn];
int ans[5*maxn], s[maxn], grau[maxn];
map<pair<int, int>, int> mapa;
int n;
vector<int> grafo[maxn];
bool marca[maxn];
int32_t main() {
int m;
cin >> n >> m;
if(m > n) {
cout << "0\n";
return 0;
}
int total = 0;
for(int i=1;i<=n;i++)
cin >> s[i], s[i] *= 2, total += s[i];
for(int i=1;i<=m;i++) {
int a, b;
cin >> a >> b;
grafo[a].push_back(b);
grafo[b].push_back(a);
mapa[{a, b}] = i;
mapa[{b, a}] = i;
grau[a]++;
grau[b]++;
}
queue<int> fila;
for(int i=1;i<=n;i++) {
if(grau[i] == 1)
fila.push(i);
}
while(!fila.empty()) {
int u = fila.front();
fila.pop();
if(mark[u]) continue;
mark[u] = true;
// cout << u << ": " << s[u] << "\n";
for(auto v : grafo[u]) {
if(mark[v]) continue;
grau[v]--;
ans[mapa[{u, v}]] = s[u], s[v] -= s[u];
if(grau[v] == 1) fila.push(v);
}
}
vector<int> ciclo;
for(int i=1;i<=n;i++)
if(!mark[i]) ciclo.push_back(i);
if(ciclo.size() == 0) {
for(int i=1;i<=m;i++)
cout << ans[i] << "\n";
return 0;
}
// cout << "SHITE\n"
if(ciclo.size() % 2 == 0){
cout << "0\n";
return 0;
}
vector<int> ordem;
int k = 0;
ordem.push_back(ciclo[0]);
while(k < ordem.size()) {
int u = ordem[k++];
if(marca[u]) continue;
marca[u] = true;
for(auto v : grafo[u]) {
if(mark[v] || marca[v]) continue;
ordem.push_back(v);
break;
}
}
int sums = 0;
int val = 1;
for(auto u : ordem) {
sums += (s[u] * val);
val *= -1;
}
sums >>= 1;
ans[mapa[{ordem.back(), ordem.front()}]] = sums;
int l = sums;
for(int i = 0; i < (int)ordem.size() - 1;i++) {
ans[mapa[{ordem[i], ordem[i+1]}]] = s[ordem[i]] - l;
l = s[ordem[i]] - l;
}
for(int i=1;i<=m;i++)
cout << ans[i] << "\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
pipes.cpp: In function 'int32_t main()':
pipes.cpp:80:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(k < ordem.size()) {
~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |