# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
855001 | 2023-09-29T18:22:36 Z | hariaakas646 | Pipes (BOI13_pipes) | C++17 | 70 ms | 16984 KB |
#include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, j, k) for (int i = j; i < k; i++) #define frange(i, j) forr(i, 0, j) #define all(cont) cont.begin(), cont.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long int lli; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<lli> vll; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vi> vvi; typedef map<int, int> mpii; typedef set<int> seti; typedef multiset<int> mseti; typedef long double ld; void usaco() { freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin); // freopen("problem.out", "w", stdout); } int main() { // usaco(); int n, m; scd(n); scd(m); vll vec(n+1); forr(i, 1, n+1) sclld(vec[i]); if(m > n) { printf("0"); return 0; } vector<set<pii>> graph(n+1); vi deg(n+1); frange(i, m) { int a, b; scd(a); scd(b); graph[a].insert(mp(b, i)); graph[b].insert(mp(a, i)); deg[a]++; deg[b]++; } vll out(m); queue<int> q; forr(i, 1, n+1) { if(deg[i] == 1) q.push(i); } vb cyc(n+1, true); vb vis(n+1); while(q.size()) { auto x = q.front(); q.pop(); cyc[x] = false; vis[x] = true; for(auto p : graph[x]) { graph[p.f].erase(mp(x, p.s)); deg[p.f]--; out[p.s] = 2*vec[x]; vec[p.f] -= vec[x]; if(deg[p.f] == 1) q.push(p.f); } } int c = 0; forr(i, 1, n+1) { if(cyc[i]) c++; } if(c % 2==0) { printf("0"); return 0; } forr(i, 1, n+1) { if(cyc[i]) { pii p = (*graph[i].begin()); int x = p.f; int ed = p.s; lli k = 0; while(x != i) { k = vec[x] - k; x = (*graph[x].begin()).f; } lli v = (vec[i] - k)/2; out[ed] = 2 * v; x = (*graph[i].begin()).f; while(x != i) { v = vec[x] - v; pii p = *graph[x].begin(); out[p.s] = 2*v; x = p.f; } break; } } frange(i, m) printf("%lld\n", out[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | Output isn't correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Incorrect | 1 ms | 344 KB | Output isn't correct |
4 | Incorrect | 56 ms | 16528 KB | Output isn't correct |
5 | Incorrect | 1 ms | 348 KB | Output isn't correct |
6 | Incorrect | 1 ms | 348 KB | Output isn't correct |
7 | Incorrect | 1 ms | 360 KB | Output isn't correct |
8 | Incorrect | 0 ms | 348 KB | Output isn't correct |
9 | Incorrect | 1 ms | 348 KB | Output isn't correct |
10 | Incorrect | 1 ms | 348 KB | Output isn't correct |
11 | Incorrect | 1 ms | 348 KB | Output isn't correct |
12 | Incorrect | 1 ms | 348 KB | Output isn't correct |
13 | Incorrect | 46 ms | 13220 KB | Output isn't correct |
14 | Incorrect | 60 ms | 15708 KB | Output isn't correct |
15 | Incorrect | 60 ms | 16724 KB | Output isn't correct |
16 | Incorrect | 48 ms | 14164 KB | Output isn't correct |
17 | Incorrect | 58 ms | 16536 KB | Output isn't correct |
18 | Incorrect | 58 ms | 16468 KB | Output isn't correct |
19 | Incorrect | 51 ms | 16456 KB | Output isn't correct |
20 | Incorrect | 0 ms | 348 KB | Output isn't correct |
21 | Incorrect | 1 ms | 348 KB | Output isn't correct |
22 | Incorrect | 56 ms | 16708 KB | Output isn't correct |
23 | Incorrect | 51 ms | 13136 KB | Output isn't correct |
24 | Incorrect | 60 ms | 16732 KB | Output isn't correct |
25 | Incorrect | 48 ms | 13888 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 344 KB | Output isn't correct |
2 | Incorrect | 1 ms | 420 KB | Output isn't correct |
3 | Correct | 45 ms | 15676 KB | Output is correct |
4 | Correct | 7 ms | 1116 KB | Output is correct |
5 | Correct | 7 ms | 1116 KB | Output is correct |
6 | Correct | 8 ms | 1116 KB | Output is correct |
7 | Incorrect | 0 ms | 348 KB | Output isn't correct |
8 | Incorrect | 0 ms | 348 KB | Output isn't correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Incorrect | 0 ms | 348 KB | Output isn't correct |
15 | Incorrect | 1 ms | 348 KB | Output isn't correct |
16 | Incorrect | 1 ms | 348 KB | Output isn't correct |
17 | Correct | 1 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Incorrect | 1 ms | 348 KB | Output isn't correct |
23 | Incorrect | 42 ms | 13560 KB | Output isn't correct |
24 | Incorrect | 59 ms | 16720 KB | Output isn't correct |
25 | Correct | 51 ms | 15556 KB | Output is correct |
26 | Correct | 7 ms | 1116 KB | Output is correct |
27 | Correct | 7 ms | 1216 KB | Output is correct |
28 | Correct | 9 ms | 1232 KB | Output is correct |
29 | Correct | 9 ms | 1116 KB | Output is correct |
30 | Incorrect | 54 ms | 16480 KB | Output isn't correct |
31 | Incorrect | 58 ms | 16912 KB | Output isn't correct |
32 | Incorrect | 67 ms | 16984 KB | Output isn't correct |
33 | Correct | 48 ms | 16472 KB | Output is correct |
34 | Correct | 7 ms | 1112 KB | Output is correct |
35 | Correct | 7 ms | 1112 KB | Output is correct |
36 | Correct | 7 ms | 1112 KB | Output is correct |
37 | Correct | 7 ms | 1116 KB | Output is correct |
38 | Incorrect | 57 ms | 16832 KB | Output isn't correct |
39 | Incorrect | 70 ms | 16972 KB | Output isn't correct |
40 | Incorrect | 58 ms | 16720 KB | Output isn't correct |
41 | Correct | 48 ms | 16328 KB | Output is correct |
42 | Correct | 7 ms | 1116 KB | Output is correct |
43 | Correct | 10 ms | 1116 KB | Output is correct |
44 | Correct | 7 ms | 1112 KB | Output is correct |
45 | Correct | 4 ms | 604 KB | Output is correct |
46 | Incorrect | 55 ms | 16748 KB | Output isn't correct |
47 | Incorrect | 57 ms | 16888 KB | Output isn't correct |
48 | Incorrect | 56 ms | 16692 KB | Output isn't correct |
49 | Correct | 53 ms | 15696 KB | Output is correct |
50 | Correct | 12 ms | 1116 KB | Output is correct |
51 | Correct | 7 ms | 1228 KB | Output is correct |
52 | Correct | 7 ms | 1116 KB | Output is correct |
53 | Correct | 5 ms | 860 KB | Output is correct |
54 | Incorrect | 63 ms | 16580 KB | Output isn't correct |