# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
854997 | 2023-09-29T18:08:32 Z | hariaakas646 | Pipes (BOI13_pipes) | C++17 | 76 ms | 17864 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); vi vec(n+1); forr(i, 1, n+1) scd(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]++; } vi 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); } } forr(i, 1, n+1) { if(cyc[i]) { pii p = (*graph[i].begin()); int x = p.f; int ed = p.s; int k = 0; while(x != i) { k = vec[x] - k; x = (*graph[x].begin()).f; } int v = (n - 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("%d\n", out[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 604 KB | Output is correct |
4 | Correct | 66 ms | 17864 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 604 KB | Output is correct |
12 | Correct | 1 ms | 604 KB | Output is correct |
13 | Correct | 54 ms | 14220 KB | Output is correct |
14 | Correct | 60 ms | 16724 KB | Output is correct |
15 | Correct | 65 ms | 17704 KB | Output is correct |
16 | Correct | 53 ms | 15184 KB | Output is correct |
17 | Correct | 70 ms | 17664 KB | Output is correct |
18 | Correct | 64 ms | 17748 KB | Output is correct |
19 | Correct | 59 ms | 17564 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 69 ms | 17748 KB | Output is correct |
23 | Correct | 50 ms | 14040 KB | Output is correct |
24 | Correct | 63 ms | 17744 KB | Output is correct |
25 | Correct | 52 ms | 14900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Incorrect | 1 ms | 448 KB | Output isn't correct |
3 | Incorrect | 63 ms | 16720 KB | Output isn't correct |
4 | Correct | 7 ms | 1372 KB | Output is correct |
5 | Correct | 7 ms | 1324 KB | Output is correct |
6 | Correct | 8 ms | 1368 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 | Incorrect | 0 ms | 348 KB | Output isn't 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 | Incorrect | 1 ms | 348 KB | Output isn't correct |
18 | Correct | 0 ms | 344 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 | 44 ms | 14164 KB | Output isn't correct |
24 | Incorrect | 71 ms | 17580 KB | Output isn't correct |
25 | Incorrect | 55 ms | 16724 KB | Output isn't correct |
26 | Correct | 7 ms | 1336 KB | Output is correct |
27 | Correct | 7 ms | 1368 KB | Output is correct |
28 | Correct | 7 ms | 1372 KB | Output is correct |
29 | Correct | 8 ms | 1372 KB | Output is correct |
30 | Incorrect | 54 ms | 17184 KB | Output isn't correct |
31 | Incorrect | 50 ms | 17376 KB | Output isn't correct |
32 | Incorrect | 63 ms | 17688 KB | Output isn't correct |
33 | Incorrect | 55 ms | 17740 KB | Output isn't correct |
34 | Correct | 7 ms | 1372 KB | Output is correct |
35 | Correct | 8 ms | 1368 KB | Output is correct |
36 | Correct | 7 ms | 1372 KB | Output is correct |
37 | Correct | 8 ms | 1332 KB | Output is correct |
38 | Incorrect | 57 ms | 17596 KB | Output isn't correct |
39 | Incorrect | 76 ms | 17576 KB | Output isn't correct |
40 | Incorrect | 67 ms | 17488 KB | Output isn't correct |
41 | Incorrect | 50 ms | 17448 KB | Output isn't correct |
42 | Correct | 7 ms | 1372 KB | Output is correct |
43 | Correct | 7 ms | 1372 KB | Output is correct |
44 | Correct | 7 ms | 1372 KB | Output is correct |
45 | Correct | 4 ms | 1116 KB | Output is correct |
46 | Incorrect | 53 ms | 17544 KB | Output isn't correct |
47 | Incorrect | 60 ms | 17660 KB | Output isn't correct |
48 | Incorrect | 51 ms | 17460 KB | Output isn't correct |
49 | Incorrect | 59 ms | 16724 KB | Output isn't correct |
50 | Correct | 7 ms | 1368 KB | Output is correct |
51 | Correct | 7 ms | 1460 KB | Output is correct |
52 | Correct | 7 ms | 1372 KB | Output is correct |
53 | Correct | 5 ms | 1204 KB | Output is correct |
54 | Incorrect | 52 ms | 17500 KB | Output isn't correct |