이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#endif
typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 1e5 + 5;
int n, m;
vector<int> c;
vector<set<int>> adj;
vector<pii> e;
vector<ll> ans;
int adjacentNode(int node, int i) {
assert(i == 0 || i == 1);
int adj_edge = (i == 0 ? *adj[node].begin() : *adj[node].rbegin());
int adj_node = e[adj_edge].x ^ e[adj_edge].y ^ node;
return adj_node;
}
void dfs(int at, int p, int root, vector<pii> &order) {
int nxt;
nxt = adjacentNode(at, 0);
if (nxt != p) order.push_back({at, *adj[at].begin()});
else {
nxt = adjacentNode(at, 1);
if (nxt != p) order.push_back({at, *adj[at].rbegin()});
}
if (nxt != root) dfs(nxt, at, root, order);
}
int main() {
#ifdef LOCAL
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
scanf("%d %d", &n, &m);
c.resize(n);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
adj.resize(n);
e.resize(m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--, v--;
adj[u].insert(i);
adj[v].insert(i);
e[i] = {u, v};
}
ans.resize(m);
queue<int> q;
for (int i = 0; i < n; i++) q.push(i);
while (!q.empty()) {
int curr_node = q.front(); q.pop();
if (adj[curr_node].size() == 1) {
int adj_edge = *adj[curr_node].begin();
int adj_node = adjacentNode(curr_node, 0);
ans[adj_edge] = 2LL * c[curr_node];
c[curr_node] -= ans[adj_edge] / 2;
c[adj_node] -= ans[adj_edge] / 2;
adj[curr_node].erase(adj_edge);
adj[adj_node].erase(adj_edge);
if (adj[adj_node].size() == 1) q.push(adj_node);
}
}
int cnt_node = 0;
for (int i = 0; i < n; i++) {
if (adj[i].size() > 2) {
printf("0\n");
return 0;
}
cnt_node += adj[i].size() == 2;
}
if (cnt_node > 0 && cnt_node % 2 == 0) {
printf("0\n");
return 0;
}
int first_node;
for (first_node = 0; first_node < n; first_node++) {
if (adj[first_node].size() == 2) break;
}
if (first_node < n) {
vector<pii> order;
dfs(first_node, -1, first_node, order);
ll sum = 2LL * c[first_node];
ll diff = 0;
for (int i = 1; i < order.size(); i++) {
diff = 2LL * c[order[i].x] - diff;
}
ans[order[0].y] = (sum - diff) / 2LL;
for (int i = 1; i < order.size(); i++) {
ans[order[i].y] = 2LL * c[order[i].x] - ans[order[i - 1].y];
}
}
for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
pipes.cpp: In function 'int main()':
pipes.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < order.size(); i++) {
~~^~~~~~~~~~~~~~
pipes.cpp:117:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < order.size(); i++) {
~~^~~~~~~~~~~~~~
pipes.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:52:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
~~~~~^~~~~~~~~~~~~
pipes.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |