제출 #49167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49167		aome	Pipes (BOI13_pipes)	C++17	100 / 100	371 ms	22076 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, m;
int a[N];
int par[N];
int deg[N];
int res[N];
bool vis[N];
vector< pair<int, int> > G[N];
map< pair<int, int>, int > mp;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	if (m > n) {
		cout << 0; return 0;
	}
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back({v, i});
		G[v].push_back({u, i});
		deg[u]++, deg[v]++;
		mp[{u, v}] = mp[{v, u}] = i;
	}
	queue<int> qu;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 1) qu.push(i);
	}
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto v : G[u]) {
			if (par[v.first] == u) continue;
			deg[v.first]--, par[u] = v.first;
			a[v.first] -= a[u], res[v.second] = a[u];
			if (deg[v.first] == 1) qu.push(v.first);
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (deg[i] != 2) continue;
		int u = i;
		vector<int> ver;
		while (1) {
			bool found = 0;
			vis[u] = 1, ver.push_back(u);
			for (auto v : G[u]) {
				if (deg[v.first] == 2 && !vis[v.first]) {
					u = v.first, found = 1; break;
				}
			}
			if (!found) break; 
		}
		int sz = ver.size();
		if (sz % 2 == 0) {
			cout << 0; return 0;
		}
		vector<int> edg;
		for (int j = 0; j < sz; ++j) {
			edg.push_back(mp[{ver[j], ver[(j + 1) % sz]}]);
		}
		res[edg[0]] = 0;
		for (int j = 1; j < sz; ++j) {
			res[edg[j]] = a[ver[j]] - res[edg[j - 1]];
		}
		if ((res[edg[sz - 1]] & 1) != (a[ver[0]] & 1)) {
			cout << 0; return 0;
		}
		res[edg[0]] = (a[ver[0]] - res[edg[sz - 1]]) / 2;
		for (int j = 1; j < sz; ++j) {
			res[edg[j]] = a[ver[j]] - res[edg[j - 1]];
		}
		break;
	}
	for (int i = 1; i <= m; ++i) cout << res[i] * 2 << ' ';
}

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