| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 447748 |
2021-07-27T12:49:13 Z |
prvocislo |
Pipes (BOI13_pipes) |
C++17 |
|
84 ms |
19424 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void end()
{
cout << 0 << endl;
exit(0);
}
const int maxn = 1e5 + 5;
vector<pair<int, int> > g[maxn];
int deg[maxn], vis[maxn], n[maxn], e[maxn];
ll sum[maxn*2];
vector<int> cy;
void dfs(int u, int p, int st)
{
if (u == st && p != -1) return;
sum[cy.size()] = n[u];
for (pair<int, int> v : g[u]) if (!vis[v.first] && v.first != p)
{
cy.push_back(v.second);
dfs(v.first, u, st);
if (u == st) return;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
if (M > N) end();
for (int i = 0; i < N; i++) cin >> n[i];
for (int i = 0, u, v; i < M; i++)
{
cin >> u >> v;
g[--u].push_back({--v, i}), g[v].push_back({u, i});
deg[u]++, deg[v]++;
}
vector<int> stk;
for (int i = 0; i < N; i++) if (deg[i] == 1) stk.push_back(i);
while (!stk.empty())
{
int u = stk.back(); stk.pop_back();
vis[u] = true;
for (pair<int, int> v : g[u]) if (!vis[v.first])
{
e[v.second] = n[u]*2;
n[v.first] -= n[u];
deg[v.first]--;
if (deg[v.first] == 1) stk.push_back(v.first);
}
}
if (N == M) // ostal nam cyklus
{
for (int i = 0; i < N; i++) if (!vis[i])
{
dfs(i, -1, i);
break;
}
int k = cy.size();
if (!(k&1)) end();
for (int i = k; i < 2*k; i++) sum[i] = sum[i-cy.size()];
for (int i = 0; i < 2*k; i++) if (i&1) sum[i] *= -1;
for (int i = 1; i < 2*k; i++) sum[i] += sum[i-1];
for (int i = 0; i < k; i++)
{
e[cy[i]] = sum[i+k]-sum[i];
if (!(i&1)) e[cy[i]] *= -1;
}
}
for (int i = 0; i < M; i++) cout << e[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
67 ms |
10184 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2588 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2672 KB |
Output is correct |
| 13 |
Correct |
52 ms |
8728 KB |
Output is correct |
| 14 |
Correct |
63 ms |
9792 KB |
Output is correct |
| 15 |
Correct |
71 ms |
10304 KB |
Output is correct |
| 16 |
Correct |
62 ms |
9112 KB |
Output is correct |
| 17 |
Correct |
67 ms |
10240 KB |
Output is correct |
| 18 |
Correct |
83 ms |
10304 KB |
Output is correct |
| 19 |
Correct |
71 ms |
9384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2672 KB |
Output is correct |
| 22 |
Correct |
79 ms |
10176 KB |
Output is correct |
| 23 |
Correct |
52 ms |
8768 KB |
Output is correct |
| 24 |
Correct |
67 ms |
10296 KB |
Output is correct |
| 25 |
Correct |
57 ms |
8996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
57 ms |
13816 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2804 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 17 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2672 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 23 |
Correct |
59 ms |
14452 KB |
Output is correct |
| 24 |
Correct |
73 ms |
15732 KB |
Output is correct |
| 25 |
Correct |
57 ms |
13760 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 28 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 30 |
Correct |
71 ms |
14452 KB |
Output is correct |
| 31 |
Correct |
79 ms |
19424 KB |
Output is correct |
| 32 |
Correct |
68 ms |
11984 KB |
Output is correct |
| 33 |
Correct |
69 ms |
15176 KB |
Output is correct |
| 34 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 35 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 36 |
Correct |
2 ms |
2680 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 38 |
Correct |
81 ms |
14940 KB |
Output is correct |
| 39 |
Correct |
73 ms |
11224 KB |
Output is correct |
| 40 |
Correct |
72 ms |
15296 KB |
Output is correct |
| 41 |
Correct |
67 ms |
18280 KB |
Output is correct |
| 42 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 43 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 44 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 45 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 46 |
Correct |
72 ms |
14128 KB |
Output is correct |
| 47 |
Correct |
79 ms |
15544 KB |
Output is correct |
| 48 |
Correct |
84 ms |
19112 KB |
Output is correct |
| 49 |
Correct |
56 ms |
10812 KB |
Output is correct |
| 50 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 51 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 52 |
Correct |
2 ms |
2676 KB |
Output is correct |
| 53 |
Correct |
3 ms |
2680 KB |
Output is correct |
| 54 |
Correct |
84 ms |
13852 KB |
Output is correct |
