oj.uz

Submission #255588

# Submission time Handle Problem Language Result Execution time Memory
255588 2020-08-01T11:50:30 Z amoo_safar Pipes (BOI13_pipes) C++17
100 / 100
 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++){
                  ~~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# 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

Subtask #2
70.0 / 70.0

# 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