oj.uz

Submission #122531

# Submission time Handle Problem Language Result Execution time Memory
122531 2019-06-28T14:42:23 Z SuperJava Pipes (BOI13_pipes) C++17
30 / 100
 452 ms 30604 KB 
//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
//endfold
#define  N  (200'005)
#define MOD (1'000'000'007ll)
#define OO (1'050'000'000)
#define OOL (1'100'000'000'000'000'000ll)

//global
set<pair<ll,ll>> s;
set<pair<ll,ll>> adj[N];
ll sum[N];
ll val[N];

int main(){
	//fold
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout << setprecision(10);
	//endfold
	ll n,m;
	cin >> n >> m;
	assert(n == m+1);
	if(m > n) return cout << 0,0;
	//assert(m != n);
	rep(i,1,n+1){
		cin >> sum[i];
	}
	rep(i,0,m){
		ll u,v;
		cin >> u >> v;
		adj[u].insert({v,i});
		adj[v].insert({u,i});
	}
	rep(i,1,n+1){
		s.insert({sz(adj[i]),i});
	}
	while(sz(s) && s.begin()->first == 1){
		ll u = s.begin()->second;
		s.erase(s.begin());
		ll v = adj[u].begin()->first;
		ll edgide = adj[u].begin()->second;
		s.erase({sz(adj[v]),v});
		adj[u].erase(adj[u].begin());
		adj[v].erase({u,edgide});
		val[edgide] = sum[u];
		sum[u] = 0;
		sum[v] -= val[edgide];
		s.insert({sz(adj[v]),v});
	}
	//assert(sz(s) == 0);
	rep(i,0,m){
		cout << val[i]*2 << endl;
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:54:2: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
  if(m > n) return cout << 0,0;
  ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 14 ms 9984 KB Output is correct
4 Correct 307 ms 30456 KB Output is correct
5 Correct 13 ms 9728 KB Output is correct
6 Correct 11 ms 9728 KB Output is correct
7 Correct 11 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 13 ms 9984 KB Output is correct
10 Correct 10 ms 9984 KB Output is correct
11 Correct 16 ms 9984 KB Output is correct
12 Correct 11 ms 9984 KB Output is correct
13 Correct 205 ms 26272 KB Output is correct
14 Correct 452 ms 29488 KB Output is correct
15 Correct 287 ms 30588 KB Output is correct
16 Correct 236 ms 27532 KB Output is correct
17 Correct 277 ms 30456 KB Output is correct
18 Correct 297 ms 30512 KB Output is correct
19 Correct 263 ms 30584 KB Output is correct
20 Correct 10 ms 9728 KB Output is correct
21 Correct 11 ms 9984 KB Output is correct
22 Correct 291 ms 30604 KB Output is correct
23 Correct 215 ms 26388 KB Output is correct
24 Correct 270 ms 30576 KB Output is correct
25 Correct 258 ms 27008 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 27 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 22 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 22 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 22 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 23 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 21 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 22 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 21 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 21 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 21 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 21 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 25 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 20 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 20 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 20 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 20 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 22 ms 19584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 20 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 21 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 24 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 27 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 26 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 20 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 22 ms 19428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 20 ms 19452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 21 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 19 ms 19420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 27 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 44 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 20 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 21 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 28 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 22 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 21 ms 19428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 21 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 20 ms 19328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 22 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 23 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 20 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 21 ms 19436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 21 ms 19420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 21 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 26 ms 19456 KB Execution killed with signal 11 (could be triggered by violating memory limits)