# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
255588 |
2020-08-01T11:50:30 Z |
amoo_safar |
Pipes (BOI13_pipes) |
C++17 |
|
329 ms |
36032 KB |
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
ll n, m, c[N], ans[N];
vector<pll> G[N];
int mk[N];
void Solve(int u){
mk[u] = 1;
for(auto [adj, id] : G[u]){
if(!mk[adj]){
Solve(adj);
ans[id] = 2 * c[adj];
c[u] -= c[adj];
}
}
}
ll dep[N];
vector<int> vis, C;
void Find(int u, int p, int d){
mk[u] = 1;
dep[u] = d;
vis.pb(u);
for(auto [adj, id] : G[u]){
if(adj == p) continue;
if(mk[adj]){
for(int i = dep[adj]; i <= dep[u]; i++) C.pb(vis[i]);
} else Find(adj, u, d + 1);
}
vis.pop_back();
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
if(m > n) return cout << "0\n", 0;
for(int i = 1; i <= n; i++) cin >> c[i];
ll u, v;
map<pll, int> mp;
for(int i = 1; i <= m; i++){
cin >> u >> v;
G[u].pb({v, i});
G[v].pb({u, i});
mp[{u, v}] = i;
mp[{v, u}] = i;
}
if(m == n - 1){
Solve(1);
} else {
Find(1, 0, 0);
if(C.size() % 2 == 0) return cout << "0\n", 0;
memset(mk, 0, sizeof mk);
for(auto x : C) mk[x] = 1;
for(auto x : C) Solve(x);
ll a = 1, b = 0;
for(auto x : C){
b = c[x] - b;
a = -a;
}
if(b % 2 != 0) assert(false);
ll X = b / 2;
ans[mp[ {C[0], C.back() } ]] = 2 * X;
a = 1, b = 0;
for(int i = 0; i + 1 < C.size(); i++){
ll x = C[i];
b = c[x] - b;
a = -a;
ans[ mp[{C[i], C[i + 1]}] ] = 2 * (a * X + b);
}
}
for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
return 0;
}
/*
4 4
2 6 10 0
1 2
2 3
3 1
4 2
*/
Compilation message
pipes.cpp: In function 'void Find(int, int, int)':
pipes.cpp:45:19: warning: unused variable 'id' [-Wunused-variable]
for(auto [adj, id] : G[u]){
^
pipes.cpp: In function 'int main()':
pipes.cpp:87:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i + 1 < C.size(); i++){
~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5248 KB |
Output is correct |
4 |
Correct |
232 ms |
26488 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
3 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5120 KB |
Output is correct |
8 |
Correct |
3 ms |
5120 KB |
Output is correct |
9 |
Correct |
4 ms |
5248 KB |
Output is correct |
10 |
Correct |
5 ms |
5248 KB |
Output is correct |
11 |
Correct |
4 ms |
5248 KB |
Output is correct |
12 |
Correct |
4 ms |
5248 KB |
Output is correct |
13 |
Correct |
158 ms |
22212 KB |
Output is correct |
14 |
Correct |
179 ms |
25336 KB |
Output is correct |
15 |
Correct |
206 ms |
26616 KB |
Output is correct |
16 |
Correct |
168 ms |
23544 KB |
Output is correct |
17 |
Correct |
204 ms |
26488 KB |
Output is correct |
18 |
Correct |
187 ms |
26488 KB |
Output is correct |
19 |
Correct |
209 ms |
28924 KB |
Output is correct |
20 |
Correct |
4 ms |
5120 KB |
Output is correct |
21 |
Correct |
4 ms |
5376 KB |
Output is correct |
22 |
Correct |
191 ms |
26616 KB |
Output is correct |
23 |
Correct |
174 ms |
22136 KB |
Output is correct |
24 |
Correct |
185 ms |
26488 KB |
Output is correct |
25 |
Correct |
159 ms |
23032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5888 KB |
Output is correct |
2 |
Correct |
5 ms |
6144 KB |
Output is correct |
3 |
Correct |
192 ms |
29048 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5888 KB |
Output is correct |
8 |
Correct |
4 ms |
5888 KB |
Output is correct |
9 |
Correct |
4 ms |
5120 KB |
Output is correct |
10 |
Correct |
3 ms |
4992 KB |
Output is correct |
11 |
Correct |
3 ms |
4992 KB |
Output is correct |
12 |
Correct |
4 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
4992 KB |
Output is correct |
14 |
Correct |
4 ms |
5888 KB |
Output is correct |
15 |
Correct |
5 ms |
6144 KB |
Output is correct |
16 |
Correct |
5 ms |
6016 KB |
Output is correct |
17 |
Correct |
4 ms |
5376 KB |
Output is correct |
18 |
Correct |
3 ms |
5120 KB |
Output is correct |
19 |
Correct |
3 ms |
5120 KB |
Output is correct |
20 |
Correct |
3 ms |
5120 KB |
Output is correct |
21 |
Correct |
3 ms |
4992 KB |
Output is correct |
22 |
Correct |
5 ms |
6144 KB |
Output is correct |
23 |
Correct |
213 ms |
28540 KB |
Output is correct |
24 |
Correct |
240 ms |
32500 KB |
Output is correct |
25 |
Correct |
176 ms |
29048 KB |
Output is correct |
26 |
Correct |
4 ms |
5120 KB |
Output is correct |
27 |
Correct |
4 ms |
5120 KB |
Output is correct |
28 |
Correct |
3 ms |
5120 KB |
Output is correct |
29 |
Correct |
3 ms |
4992 KB |
Output is correct |
30 |
Correct |
249 ms |
34932 KB |
Output is correct |
31 |
Correct |
275 ms |
35440 KB |
Output is correct |
32 |
Correct |
214 ms |
29432 KB |
Output is correct |
33 |
Correct |
190 ms |
31224 KB |
Output is correct |
34 |
Correct |
3 ms |
5120 KB |
Output is correct |
35 |
Correct |
4 ms |
5120 KB |
Output is correct |
36 |
Correct |
4 ms |
5120 KB |
Output is correct |
37 |
Correct |
3 ms |
5120 KB |
Output is correct |
38 |
Correct |
240 ms |
34160 KB |
Output is correct |
39 |
Correct |
329 ms |
28664 KB |
Output is correct |
40 |
Correct |
244 ms |
32364 KB |
Output is correct |
41 |
Correct |
235 ms |
34088 KB |
Output is correct |
42 |
Correct |
4 ms |
5120 KB |
Output is correct |
43 |
Correct |
3 ms |
5120 KB |
Output is correct |
44 |
Correct |
3 ms |
4992 KB |
Output is correct |
45 |
Correct |
3 ms |
5120 KB |
Output is correct |
46 |
Correct |
254 ms |
36032 KB |
Output is correct |
47 |
Correct |
242 ms |
32372 KB |
Output is correct |
48 |
Correct |
263 ms |
35188 KB |
Output is correct |
49 |
Correct |
177 ms |
26232 KB |
Output is correct |
50 |
Correct |
3 ms |
5120 KB |
Output is correct |
51 |
Correct |
3 ms |
5120 KB |
Output is correct |
52 |
Correct |
3 ms |
5120 KB |
Output is correct |
53 |
Correct |
4 ms |
4992 KB |
Output is correct |
54 |
Correct |
273 ms |
33564 KB |
Output is correct |