Submission #84111

#	Time	Username	Problem	Language	Result	Execution time	Memory
84111		shoemakerjo	Pipes (BOI13_pipes)	C++14	100 / 100	262 ms	20412 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#define maxn 100010
#define pii pair<int, int>
#define maxm 500010
#define ll long long

int N, M;
vector<pii> adj[maxn];
vector<pii> adj2[maxn];
ll nums[maxn];
ll ans[maxm];
int deg[maxn];
bool del[maxn];
bool vis[maxn];

void dfstree(int u, int p) {

	for (pii vp : adj[u]) {
		if (vp.first != p) {
			dfstree(vp.first, u);
			ans[vp.second] = 2 * nums[vp.first];
			nums[u] -= ans[vp.second]/2;
		}
	}

}

void gotree() {
	dfstree(1, -1);

	for (int i = 0; i < M; i++) {
		cout << ans[i] << '\n';
	}
	cout.flush();

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
	}
	int u, v;
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		deg[u]++;
		deg[v]++;
		adj[u].push_back(pii(v, i));
		adj[v].push_back(pii(u, i));

	}

	if (M > N) {
		cout << 0 << endl;
		return 0;
	}
	if (M == N-1) {
		gotree();
		return 0;
	}

	stack<int> s;
	//do some stuff
	for (int i = 1; i <= N; i++) {
		if (deg[i] == 1) s.push(i);
	}
	while (s.size()) {
		u = s.top(); s.pop();
		del[u] = true;
		for (pii vp : adj[u]) {
			if (!del[vp.first]) {
				deg[vp.first]--;
				ans[vp.second] = 2*nums[u];
				nums[vp.first] -= ans[vp.second]/2;
				if (deg[vp.first] == 1) {
					del[vp.first] = true;
					s.push(vp.first);
				}
			}
		}
	}


	int cur;
	for (int i = 1; i <= N; i++) {
		if (!del[i]) {
			cur = i;
			for (pii vp : adj[i]) {
				if (!del[vp.first]) {
					adj2[i].push_back(vp);
				}
			}
		}
	}


	ll sum = 0;
	sum += nums[cur];
	ll mult = -1;
	int og = cur;
	int numseen = 1;
	// cout << "guy: " << nums[7] << endl;
	do {
		vis[cur] = true;
		// cout << "cur: " << cur << endl;

		for (int i = 1; i >= 0; i--) {
			pii vp = adj2[cur][i];
			if (!vis[vp.first]) {
				cur = vp.first;
				numseen++;
				// cout << "contribution: " << nums[cur] << " mult: " << mult << endl;
				sum += mult*nums[cur];
				mult *= -1LL;
				break;
			}
		}
	} while (!vis[cur]);

	// cout << "numseen: " << numseen << endl;
	if (numseen%2 == 0) {
		cout << 0 << endl;
		return 0;
	}

	fill(vis, vis+maxn, false);
	ans[adj2[og][0].second] = sum; //not sure if I have to divide by 2
	// cout << og << " to " << adj2[og][0].first << " assigned to " << sum << endl;
	cur = adj2[og][0].first;
	
	vis[og] = true;
	while (cur != og) {
		vis[cur] = true;
		for (int i = 0; i <= 1; i++) {
			pii vp = adj2[cur][i];
			if (!vis[vp.first]) {
				// cout << "looking at: " << cur << " to " << vp.first << endl;

				ans[vp.second] = 2 * (nums[cur] - 
					ans[adj2[cur][1-i].second]/2);
				cur = vp.first;
				// vis[cur] = true;
				break;
			}
		}
		if (vis[cur]) break;
	}

	for (int i = 0; i <= 1; i++) {
		pii vp = adj2[cur][i];
		if (vp.first == og) {
			ans[vp.second] = 2 * (nums[cur] - ans[adj2[cur][1-i].second]/2);
		}
	}
	for (int i = 0; i < M; i++) {
		cout << ans[i] << '\n';
	}

	cout.flush();
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:103:17: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  sum += nums[cur];
         ~~~~~~~~^

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