| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 158008 |
2019-10-14T11:59:14 Z |
DrSwad |
Pipes (BOI13_pipes) |
C++11 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
