제출 #158021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158021		DrSwad	Pipes (BOI13_pipes)	C++14	100 / 100	645 ms	63176 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#endif

typedef long long ll;
typedef pair<int, int> pii;

#define x first
#define y second

const int N = 1e5 + 5;

int n, m;
vector<int> c;
vector<set<int>> adj;
vector<pii> e;
vector<ll> ans;

int adjacentNode(int node, int i) {
	assert(i == 0 || i == 1);
	int adj_edge = (i == 0 ? *adj[node].begin() : *adj[node].rbegin());
	int adj_node = e[adj_edge].x ^ e[adj_edge].y ^ node;
	return adj_node;
}

void dfs(int at, int p, int root, vector<pii> &order) {
	int nxt;

	nxt = adjacentNode(at, 0);
	if (nxt != p) order.push_back({at, *adj[at].begin()});
	else {
		nxt = adjacentNode(at, 1);
		if (nxt != p) order.push_back({at, *adj[at].rbegin()});
	}

	if (nxt != root) dfs(nxt, at, root, order);
}

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif

	scanf("%d %d", &n, &m);

	c.resize(n);
	for (int i = 0; i < n; i++) scanf("%d", &c[i]);

	adj.resize(n);
	e.resize(m);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--, v--;
		adj[u].insert(i);
		adj[v].insert(i);
		e[i] = {u, v};
	}

	ans.resize(m);
	queue<int> q;
	for (int i = 0; i < n; i++) q.push(i);

	while (!q.empty()) {
		 int curr_node = q.front(); q.pop();
		 if (adj[curr_node].size() == 1) {
		 	int adj_edge = *adj[curr_node].begin();
		 	int adj_node = adjacentNode(curr_node, 0);

		 	ans[adj_edge] = 2LL * c[curr_node];
		 	c[curr_node] -= ans[adj_edge] / 2;
		 	c[adj_node] -= ans[adj_edge] / 2;

		 	adj[curr_node].erase(adj_edge);
		 	adj[adj_node].erase(adj_edge);

		 	if (adj[adj_node].size() == 1) q.push(adj_node);
		 }
	}

	int cnt_node = 0;
	for (int i = 0; i < n; i++) {
		if (adj[i].size() > 2) {
			printf("0\n");
			return 0;
		}
		cnt_node += adj[i].size() == 2;
	}

	if (cnt_node > 0 && cnt_node % 2 == 0) {
		printf("0\n");
		return 0;
	}

	int first_node;
	for (first_node = 0; first_node < n; first_node++) {
		if (adj[first_node].size() == 2) break;
	}

	if (first_node < n) {
		vector<pii> order;
		dfs(first_node, -1, first_node, order);

		ll sum = 2LL * c[first_node];
		ll diff = 0;
		for (int i = 1; i < order.size(); i++) {
			diff = 2LL * c[order[i].x] - diff;
		}

		ans[order[0].y] = (sum - diff) / 2LL;

		for (int i = 1; i < order.size(); i++) {
			ans[order[i].y] = 2LL * c[order[i].x] - ans[order[i - 1].y];
		}
	}

	for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'int main()':
pipes.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < order.size(); i++) {
                   ~~^~~~~~~~~~~~~~
pipes.cpp:117:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < order.size(); i++) {
                   ~~^~~~~~~~~~~~~~
pipes.cpp:49: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:52:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; i++) scanf("%d", &c[i]);
                              ~~~~~^~~~~~~~~~~~~
pipes.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

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