Submission #285732

#	Time	Username	Problem	Language	Result	Execution time	Memory
285732		kostia244	Pipes (BOI13_pipes)	C++17	70 / 100	257 ms	39916 KiB

pipes

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using ll = long long;
using namespace std;
const int maxn = 1<<19;
int n, m;
vector<array<ll, 2>> g[maxn];
ll val[maxn];
ll vis[maxn], C[maxn], h[maxn], L = -1, R, ID, bb;
ll s = 0;
void dfs(int v, int p) {
	ll cur = C[v];
	vis[v] = 1;
	if(h[v]&1) s -= C[v];
	else s += C[v];
	for(auto &[i, id] : g[v]) if(i != p) {
		if(!vis[i]) {
			h[i] = h[v]+1;
			dfs(i, v);
		} else if(h[i] < h[v]) {
			if(L != -1 || (h[i]&1) != (h[v]&1)) {cout << "0\n", exit(0);}
			L = i, R = v, ID = id, bb = h[v]&1;
		}
	}
}
ll recover(int v, int p) {
	ll cur = C[v];
	for(auto [i, id] : g[v]) if(i != p && id != ID) {
		ll t = recover(i, v);
		val[id] = t;
		cur += t;
	}
	return -cur;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> C[i];
	for(int f, t, i = 0; i < m; i++) {
		cin >> f >> t;
		g[f].push_back({t, i});
		g[t].push_back({f, i});
	}
	dfs(1, 1);
	if(L != -1) {
		//cout << ID << ":\n";
		if(bb) s *= -1;
		C[L] -= s/2;
		C[R] -= s/2;
		val[ID] = (-s)/2;
	}
	recover(1, 1);
	for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
}
//?VK
//??V
//K?

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:13:5: warning: unused variable 'cur' [-Wunused-variable]
   13 |  ll cur = C[v];
      |     ^~~
pipes.cpp: In function 'int main()':
pipes.cpp:54:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |  for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
      |  ^~~
pipes.cpp:54:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |  for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
      |                                                          ^~~~

• Subtask 1: 0 / 30
• Subtask 2: 70 / 70