제출 #1126819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126819		Halym2007	Pipes (BOI13_pipes)	C++17	0 / 100	335 ms	48564 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
ll n, m, deg[N], val[N], jog[N];
vector <int> v[N]; 
queue <int> q;
map <pii, int> mp;

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> val[i];
	}	
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r;
		if (l > r) swap (l, r);
		mp[{l, r}] = i;
		v[l].pb (r);
		v[r].pb (l);
		deg[l]++;
		deg[r]++;
	}
	
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 1) {
			q.push(i);
//			cout << i << " ";
		}
	}	
//	return 0;
	while (!q.empty()) {
		int x = q.front();
		deg[x]--;
		q.pop();
		for (int i : v[x]) {
			if (!deg[i]) continue;
			if (deg[i] == 1) {
				q.push(i);
			}
			jog[mp[{min(i, x), max (i, x)}]] = val[x];
			deg[i]--;
			val[i] -= val[x];
		}
	}
	for (int i = 1; i <= m; ++i) {
		cout << jog[i] * 2 << "\n";
	}
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70