【題解】Zerojudge f163 - 貨物分配

AC (0.8s, 30.9MB)

#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma comment(linker, "/stack:200000000")
 
using namespace std;
 
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

const int mxN = 1e6 + 1;

int n, m, x, a, b, c;
int parent[mxN << 1], w[mxN << 1];
pair<int, int> child[mxN << 1];
int q[10000];

int main() {
	fastio;
	memset(parent, 0, sizeof(parent));
	memset(w, 0, sizeof(w));
	memset(child, 0, sizeof(child));
	cin >> n >> m;
	int mx = n << 1;
	for(int i = n; i < mx; ++i)
		cin >> w[i];
	for(int i = 0; i < m; ++i)
		cin >> q[i];
	for(int i = 1; i < n; ++i) {
		cin >> a >> b >> c;
		child[a].first = b;
		child[a].second = c;
		parent[b] = a;
		parent[c] = a;
	}
	for(int i = n; i < mx; ++i) {
		int cur = parent[i];
		while(cur != 1) {
			w[cur] += w[i];
			cur = parent[cur];
		}
	}
	for(int i = 0; i < m; ++i) {
		int cur = 1;
		while(child[cur].first) {
			w[cur] += q[i];
			if(w[child[cur].first] <= w[child[cur].second])
				cur = child[cur].first;
			else
				cur = child[cur].second;
		}
		cout << cur << " ";
		w[cur] += q[i];
	}
		
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge f163 - 貨物分配