이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
const int MAXN = 1e5 + 10;
const int MAXM = 5e5 + 10;
vector<pii> adj[MAXN];
int bEdge = -1;
vector<pii> edges;
int h[MAXN];
int change[MAXN];
bool vis[MAXN];
int dad[MAXN];
int dp[MAXN];
int peso[MAXM];
void dfs(int node) {
vis[node] = 1;
for (auto [u, z] : adj[node]) {
if (u == dad[node]) continue;
if (vis[u]) bEdge = z;
else {
dad[u] = node;
h[u] = h[node] + 1;
dfs(u);
}
}
}
void calc(int node) {
vis[node] = 1;
for (auto [u, z] : adj[node]) {
if (vis[u]) continue;
calc(u);
dp[node] += (change[u] - dp[u]);
peso[z] += (change[u] - dp[u]);
}
}
vector<int> path;
bool found = 0;
int need;
void cPath(int node, int wantNode) {
vis[node] = 1;
path.push_back(node);
if (node == wantNode) {
found = 1;
return;
}
for (auto [u, z] : adj[node]) {
if (vis[u]) continue;
cPath(u, wantNode);
if (found) return;
}
path.pop_back();
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << 0 << "\n";
return 0;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> change[i];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
edges.push_back({a, b});
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
if (m > n) {
cout << "0\n";
return 0;
}
dfs(1);
int lca = 0;
if (bEdge != -1) {
auto u = edges[bEdge];
int a = u.fr, b = u.se;
if (h[a] > h[b]) swap(a, b);
// a is higher than b
int oa = a, ob = b;
while (h[b] > h[a]) {
b = dad[b];
}
while (a != b) {
a = dad[a];
b = dad[b];
}
lca = a;
a = oa;
b = ob;
int tam = h[a] + h[b] - 2*h[lca] + 1;
if ((tam % 2LL) == 0) {
cout << "0\n";
return 0;
}
}
memset(vis, 0, sizeof vis);
calc(1);
if (dp[1] == change[1]) {
for (int i = 0; i < m; i++) cout << 2*peso[i] << "\n";
return 0;
}
// first case is for tree
// second case is if you can't add 2x to it
if ((bEdge == -1) || ((change[1] - dp[1]) % 2LL)) {
cout << "0\n";
return 0;
}
need = (change[1] - dp[1])/2LL;
for (int i = 0; i < m; i++) {
cout << 2*peso[i] << "\n";
}
memset(vis, 0, sizeof vis);
cPath(1, lca);
int tam = path.size();
int inv = 1;
for (int i = 0; i < (tam - 1); i++) {
int node = path[i];
int prox = path[i + 1];
for (auto [u, z] : adj[node]) {
if (u == prox) {
peso[z] += 2*need*inv;
inv = -inv;
break;
}
}
}
int a = edges[bEdge].fr, b = edges[bEdge].se;
path.clear();
memset(vis, 0, sizeof vis);
cPath(lca, a);
tam = path.size();
int cr = inv;
for (int i = 0; i < (tam - 1); i++) {
int node = path[i];
int prox = path[i + 1];
for (auto [u, z] : adj[node]) {
if (u == prox) {
peso[z] += need*cr;
cr = -cr;
break;
}
}
}
path.clear();
memset(vis, 0, sizeof vis);
cPath(lca, b);
tam = path.size();
cr = inv;
for (int i = 0; i < (tam - 1); i++) {
int node = path[i];
int prox = path[i + 1];
for (auto [u, z] : adj[node]) {
if (u == prox) {
peso[z] += need*cr;
cr = -cr;
break;
}
}
}
if ((h[a] - h[lca]) % 2LL) inv = -inv;
peso[bEdge] += inv*need;
for (int i = 0; i < m; i++) {
cout << 2*peso[i] << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |