Submission #84257

#	Time	Username	Problem	Language	Result	Execution time	Memory
84257		IOrtroiii	Pipes (BOI13_pipes)	C++14	100 / 100	131 ms	15552 KiB

pipes

/*
input
3 3
2 2 2
1 2
2 3
3 1
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m;
int deg[N];
bool ok[N];
long long a[N], ans[N];
vector<pair<int,int>> g[N];
bool was[N];
long long sum = 0, cur = 0;
bool have;

void dfs(int u,int p,int now) {
	if (now) cur += a[u];
	was[u] = 1;
	for (auto e : g[u]) {
		int v = e.first;
		int id = e.second;
		if (v == p) continue;
		if (ok[v]) continue;
		if (was[v]) {
			if (now) {
				if (have) return;
				ans[id] = cur - sum;
				a[u] -= ans[id];
				a[v] -= ans[id];
				have = true;
			} else {
				printf("0\n"); exit(0);
			}
		}
		else {
			dfs(v, u, now ^ 1);
			ans[id] = a[v];
			a[u] -= ans[id];
			a[v] -= ans[id];
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	if (n < m) return printf("0\n"),0;
	for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
	for (int i = 1; i <= m; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		++deg[u], ++deg[v];
		g[u].push_back({v, i}), g[v].push_back({u, i});	
	}
	queue<int> q;
	for (int u = 1; u <= n; ++u) if (deg[u] == 1) {
		q.push(u);
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto e : g[u]) {
			int v = e.first;
			int id = e.second;
			if (ok[v] == false) {
				ans[id] = a[u];
				a[u] -= ans[id];
				a[v] -= ans[id];
				ok[u] = true;
				if (--deg[v] == 1) {
					q.push(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) if (ok[i] == false) sum += a[i];
	if (sum & 1) return printf("0\n"),0;
	sum /= 2;
	for (int i = 1; i <= n; ++i) if (ok[i] == false) {
		dfs(i, -1, 1); break;
	}
	for (int i = 1; i <= n; ++i) if (a[i]) return printf("0\n"),0;
	for (int i = 1; i <= m; ++i) if (ans[i] > (long long) 5e8 || ans[i] < (long long) -5e8) {
		return printf("0\n"),0;
	}
	for (int i = 1; i <= m; ++i) printf("%lld\n", 2 * ans[i]);
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:52: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:54:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
                               ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:56:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

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