oj.uz

답안 #158008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158008 2019-10-14T11:59:14 Z DrSwad Pipes (BOI13_pipes) C++11
45.3704 / 100
 669 ms 66488 KB 
#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);
	for (int i = 0; i < m; i++) {
		if (adj[e[i].x].size() == 1 || adj[e[i].y].size() == 1) {
			ans[i] = 2LL * (adj[e[i].x].size() == 1 ? c[e[i].x] : c[e[i].y]);
			adj[e[i].x].erase(i);
			adj[e[i].y].erase(i);
			c[e[i].x] -= ans[i] / 2;
			c[e[i].y] -= ans[i] / 2;
		}
	}

	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 % 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;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < order.size(); i++) {
                   ~~^~~~~~~~~~~~~~
pipes.cpp:107: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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 3 ms 504 KB Output isn't correct
4 Incorrect 111 ms 18012 KB Output isn't correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Incorrect 2 ms 252 KB Output isn't correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Incorrect 3 ms 504 KB Output isn't correct
10 Incorrect 3 ms 504 KB Output isn't correct
11 Incorrect 3 ms 504 KB Output isn't correct
12 Incorrect 3 ms 504 KB Output isn't correct
13 Incorrect 77 ms 14392 KB Output isn't correct
14 Incorrect 86 ms 16888 KB Output isn't correct
15 Incorrect 95 ms 17892 KB Output isn't correct
16 Incorrect 83 ms 15388 KB Output isn't correct
17 Incorrect 91 ms 17788 KB Output isn't correct
18 Incorrect 91 ms 17912 KB Output isn't correct
19 Incorrect 87 ms 17912 KB Output isn't correct
20 Incorrect 2 ms 376 KB Output isn't correct
21 Incorrect 3 ms 504 KB Output isn't correct
22 Incorrect 100 ms 17940 KB Output isn't correct
23 Incorrect 72 ms 14360 KB Output isn't correct
24 Incorrect 98 ms 17884 KB Output isn't correct
25 Incorrect 85 ms 15096 KB Output isn't correct

Subtask #2
45.3703703704 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 3 ms 504 KB Output isn't correct
3 Correct 96 ms 16956 KB Output is correct
4 Correct 100 ms 17812 KB Output is correct
5 Correct 102 ms 17680 KB Output is correct
6 Correct 604 ms 66488 KB Output is correct
7 Incorrect 2 ms 252 KB Output isn't correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 Incorrect 3 ms 504 KB Output isn't correct
16 Incorrect 3 ms 504 KB Output isn't correct
17 Correct 3 ms 504 KB Output is correct
18 Correct 3 ms 504 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 3 ms 504 KB Output is correct
21 Correct 4 ms 632 KB Output is correct
22 Incorrect 3 ms 504 KB Output isn't correct
23 Incorrect 74 ms 14684 KB Output isn't correct
24 Incorrect 102 ms 17932 KB Output isn't correct
25 Correct 95 ms 16916 KB Output is correct
26 Correct 99 ms 17996 KB Output is correct
27 Correct 96 ms 17808 KB Output is correct
28 Correct 104 ms 18168 KB Output is correct
29 Correct 476 ms 54540 KB Output is correct
30 Incorrect 86 ms 17656 KB Output isn't correct
31 Incorrect 102 ms 17912 KB Output isn't correct
32 Incorrect 102 ms 17888 KB Output isn't correct
33 Correct 97 ms 17912 KB Output is correct
34 Correct 99 ms 18040 KB Output is correct
35 Correct 101 ms 18004 KB Output is correct
36 Correct 100 ms 18040 KB Output is correct
37 Correct 625 ms 66424 KB Output is correct
38 Incorrect 93 ms 17992 KB Output isn't correct
39 Incorrect 99 ms 17896 KB Output isn't correct
40 Incorrect 90 ms 17912 KB Output isn't correct
41 Correct 90 ms 17912 KB Output is correct
42 Correct 86 ms 18040 KB Output is correct
43 Correct 89 ms 17912 KB Output is correct
44 Correct 101 ms 17656 KB Output is correct
45 Correct 669 ms 56948 KB Output is correct
46 Incorrect 94 ms 17912 KB Output isn't correct
47 Incorrect 90 ms 17912 KB Output isn't correct
48 Incorrect 94 ms 17956 KB Output isn't correct
49 Correct 106 ms 16888 KB Output is correct
50 Correct 92 ms 18040 KB Output is correct
51 Correct 106 ms 17900 KB Output is correct
52 Correct 88 ms 17784 KB Output is correct
53 Correct 556 ms 58864 KB Output is correct
54 Incorrect 97 ms 17656 KB Output isn't correct