답안 #122531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122531	2019-06-28T14:42:23 Z	SuperJava	Pipes (BOI13_pipes)	C++17	30 / 100	452 ms	30604 KB

pipes

//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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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)