| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 158004 |
2019-10-14T11:30:34 Z |
DrSwad |
Pipes (BOI13_pipes) |
C++14 |
|
761 ms |
66516 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;
}
}
for (int i = 0; i < n; i++) {
if (adj[i].size() > 2) {
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:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < order.size(); i++) {
~~^~~~~~~~~~~~~~
pipes.cpp:100: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 |
102 ms |
17912 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 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 |
87 ms |
14320 KB |
Output isn't correct |
| 14 |
Incorrect |
95 ms |
16892 KB |
Output isn't correct |
| 15 |
Incorrect |
100 ms |
17912 KB |
Output isn't correct |
| 16 |
Incorrect |
83 ms |
15224 KB |
Output isn't correct |
| 17 |
Incorrect |
103 ms |
17944 KB |
Output isn't correct |
| 18 |
Incorrect |
105 ms |
18040 KB |
Output isn't correct |
| 19 |
Incorrect |
94 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 |
105 ms |
18056 KB |
Output isn't correct |
| 23 |
Incorrect |
76 ms |
14280 KB |
Output isn't correct |
| 24 |
Incorrect |
100 ms |
18040 KB |
Output isn't correct |
| 25 |
Incorrect |
81 ms |
14920 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 |
87 ms |
16984 KB |
Output is correct |
| 4 |
Correct |
123 ms |
17912 KB |
Output is correct |
| 5 |
Correct |
95 ms |
17540 KB |
Output is correct |
| 6 |
Correct |
601 ms |
66516 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
380 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 |
348 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 |
2 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 |
508 KB |
Output is correct |
| 21 |
Correct |
4 ms |
660 KB |
Output is correct |
| 22 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 23 |
Incorrect |
68 ms |
14712 KB |
Output isn't correct |
| 24 |
Incorrect |
93 ms |
17916 KB |
Output isn't correct |
| 25 |
Correct |
115 ms |
17016 KB |
Output is correct |
| 26 |
Correct |
96 ms |
17932 KB |
Output is correct |
| 27 |
Correct |
90 ms |
17784 KB |
Output is correct |
| 28 |
Correct |
115 ms |
18552 KB |
Output is correct |
| 29 |
Correct |
489 ms |
54520 KB |
Output is correct |
| 30 |
Incorrect |
80 ms |
17528 KB |
Output isn't correct |
| 31 |
Incorrect |
90 ms |
17912 KB |
Output isn't correct |
| 32 |
Incorrect |
113 ms |
17856 KB |
Output isn't correct |
| 33 |
Correct |
87 ms |
17884 KB |
Output is correct |
| 34 |
Correct |
123 ms |
17912 KB |
Output is correct |
| 35 |
Correct |
101 ms |
17912 KB |
Output is correct |
| 36 |
Correct |
117 ms |
18044 KB |
Output is correct |
| 37 |
Correct |
694 ms |
66508 KB |
Output is correct |
| 38 |
Incorrect |
88 ms |
17912 KB |
Output isn't correct |
| 39 |
Incorrect |
101 ms |
17784 KB |
Output isn't correct |
| 40 |
Incorrect |
135 ms |
18040 KB |
Output isn't correct |
| 41 |
Correct |
95 ms |
17916 KB |
Output is correct |
| 42 |
Correct |
84 ms |
17896 KB |
Output is correct |
| 43 |
Correct |
123 ms |
17916 KB |
Output is correct |
| 44 |
Correct |
121 ms |
17620 KB |
Output is correct |
| 45 |
Correct |
761 ms |
57136 KB |
Output is correct |
| 46 |
Incorrect |
87 ms |
17912 KB |
Output isn't correct |
| 47 |
Incorrect |
92 ms |
18040 KB |
Output isn't correct |
| 48 |
Incorrect |
92 ms |
17912 KB |
Output isn't correct |
| 49 |
Correct |
94 ms |
17016 KB |
Output is correct |
| 50 |
Correct |
87 ms |
17912 KB |
Output is correct |
| 51 |
Correct |
94 ms |
18040 KB |
Output is correct |
| 52 |
Correct |
89 ms |
17656 KB |
Output is correct |
| 53 |
Correct |
551 ms |
58872 KB |
Output is correct |
| 54 |
Incorrect |
139 ms |
17656 KB |
Output isn't correct |
