oj.uz

Submission #122530

# Submission time Handle Problem Language Result Execution time Memory
122530 2019-06-28T14:41:24 Z SuperJava Pipes (BOI13_pipes) C++17
30 / 100
 322 ms 32288 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;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9728 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Correct 13 ms 9984 KB Output is correct
4 Correct 266 ms 31964 KB Output is correct
5 Correct 10 ms 9756 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Correct 11 ms 9984 KB Output is correct
11 Correct 11 ms 9984 KB Output is correct
12 Correct 11 ms 9984 KB Output is correct
13 Correct 196 ms 27484 KB Output is correct
14 Correct 239 ms 30880 KB Output is correct
15 Correct 259 ms 32288 KB Output is correct
16 Correct 220 ms 28816 KB Output is correct
17 Correct 284 ms 32120 KB Output is correct
18 Correct 257 ms 32276 KB Output is correct
19 Correct 206 ms 32120 KB Output is correct
20 Correct 10 ms 9728 KB Output is correct
21 Correct 11 ms 9956 KB Output is correct
22 Correct 281 ms 32084 KB Output is correct
23 Correct 212 ms 27384 KB Output is correct
24 Correct 322 ms 32120 KB Output is correct
25 Correct 216 ms 28408 KB Output is correct

Subtask #2
0 / 70.0

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