oj.uz

답안 #122961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122961 2019-06-29T17:08:59 Z SuperJava Pipes (BOI13_pipes) C++17
65 / 100
 918 ms 131076 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];

vector<ll> res;

void dfs(ll u,ll p){
	res.push_back(u);
	for(auto v:adj[u]){
		if(v.first != p) dfs(v.first,u);
	}
}

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 253 ms 32164 KB Output is correct
5 Correct 10 ms 9720 KB Output is correct
6 Correct 10 ms 9724 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 10 ms 9848 KB Output is correct
9 Correct 11 ms 9976 KB Output is correct
10 Correct 11 ms 9976 KB Output is correct
11 Correct 11 ms 9976 KB Output is correct
12 Correct 11 ms 9976 KB Output is correct
13 Correct 192 ms 27404 KB Output is correct
14 Correct 227 ms 30968 KB Output is correct
15 Correct 238 ms 32120 KB Output is correct
16 Correct 209 ms 28700 KB Output is correct
17 Correct 274 ms 32088 KB Output is correct
18 Correct 241 ms 32120 KB Output is correct
19 Correct 205 ms 32076 KB Output is correct
20 Correct 10 ms 9720 KB Output is correct
21 Correct 12 ms 9976 KB Output is correct
22 Correct 237 ms 32120 KB Output is correct
23 Correct 183 ms 27388 KB Output is correct
24 Correct 296 ms 32080 KB Output is correct
25 Correct 260 ms 28280 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 139 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 178 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 770 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 10 ms 9592 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 10 ms 9724 KB Output is correct
7 Runtime error 141 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 135 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 142 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Correct 10 ms 9720 KB Output is correct
11 Correct 10 ms 9720 KB Output is correct
12 Correct 10 ms 9720 KB Output is correct
13 Correct 10 ms 9720 KB Output is correct
14 Runtime error 139 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 180 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 166 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 163 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Correct 10 ms 9720 KB Output is correct
19 Correct 10 ms 9720 KB Output is correct
20 Correct 10 ms 9720 KB Output is correct
21 Correct 10 ms 9720 KB Output is correct
22 Runtime error 165 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 752 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 798 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 745 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Correct 10 ms 9720 KB Output is correct
27 Correct 10 ms 9724 KB Output is correct
28 Correct 10 ms 9720 KB Output is correct
29 Correct 10 ms 9720 KB Output is correct
30 Runtime error 666 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 720 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 497 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 918 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Correct 10 ms 9720 KB Output is correct
35 Correct 10 ms 9720 KB Output is correct
36 Correct 10 ms 9720 KB Output is correct
37 Correct 10 ms 9720 KB Output is correct
38 Runtime error 713 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 503 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 827 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 760 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Correct 10 ms 9720 KB Output is correct
43 Correct 10 ms 9724 KB Output is correct
44 Correct 10 ms 9720 KB Output is correct
45 Correct 10 ms 9720 KB Output is correct
46 Runtime error 728 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 787 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 710 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Runtime error 515 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Correct 10 ms 9720 KB Output is correct
51 Correct 10 ms 9720 KB Output is correct
52 Correct 10 ms 9720 KB Output is correct
53 Correct 10 ms 9796 KB Output is correct
54 Runtime error 562 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)