제출 #966660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966660		biximo	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	1206 ms	46432 KiB

designated_cities

#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000000000000LL
using namespace std;
typedef long long ll;
bool vs[N];
struct P {
	int to, cto, cfr;
};
vector<P> adj[N];
int tree_sz[N];
void sz_DFS(int c, int pr) {
	tree_sz[c] = 1;
	for(auto&i: adj[c]) {
		if(vs[i.to] || i.to == pr) continue;
		sz_DFS(i.to, c);
		tree_sz[c] += tree_sz[i.to];
	}
}
int find_cent(int c, int pr, int sz) {
	for(auto&i: adj[c]) {
		if(i.to == pr || vs[i.to] || tree_sz[i.to]*2 < sz) continue;
		 return find_cent(i.to, c, sz);
	}
	return c;
}
vector<ll> vals[N];
priority_queue<ll> pq1, pq2;
ll initVal, ans[N];
ll update_DFS(int c, int pr) {
	ll sum = 0;
	vals[c].clear();
	for(auto&i: adj[c]) {
		if(i.to == pr || vs[i.to]) continue;
		sum += i.cfr;
		sum += update_DFS(i.to, c);
		vals[c].push_back(vals[i.to].back()+i.cfr);
	}
	if(vals[c].empty()) vals[c].push_back(0);
	sort(vals[c].begin(),vals[c].end());
	for(ll i: vals[c]) pq1.push(i);
	if(pr == -1) {
		if(vals[c].size() < 2) {
			initVal = -INF;
			pq2 = priority_queue<ll>();
		} else {
			initVal = vals[c].back(); vals[c].pop_back();
			initVal += vals[c].back(); vals[c].pop_back();
			for(ll i: vals[c]) pq2.push(i);
		}
	} else {
		for(ll i: vals[c]) pq2.push(i);
	}
	return sum;
}
ll getSum(int c, int pr) {
	ll sum = 0;
	for(auto&i: adj[c]) {
		if(vs[i.to] || i.to == pr) continue;
		sum += i.cfr + getSum(i.to, c);
	}
	return sum;
}
vector<ll> updateVals(int rt, ll cum) {
	ll sum = update_DFS(rt, -1);
	ans[2] = min(ans[2], cum+sum-initVal);
	for(int i = 3; pq2.size(); i ++, pq2.pop()) {
		initVal += pq2.top();
		ans[i] = min(ans[i], cum+sum-initVal);
	}
	ans[1] = min(ans[1], cum+sum);
	initVal = 0;
	for(int i = 2; pq1.size(); i ++, pq1.pop()) {
		initVal += pq1.top();
		ans[i] = min(ans[i],cum+sum-initVal);
	}
	vector<ll> cs;
	for(auto&i: adj[rt]) {
		if(vs[i.to]) continue;
		cs.push_back(getSum(i.to,rt)+i.cfr);
	}
	return cs;
}
void DNC(int c, ll cum) {
	sz_DFS(c, -1);
	int cent = find_cent(c, -1, tree_sz[c]);
	vector<ll> sms = updateVals(cent, cum);
	for(ll i: sms) cum += i;
	auto it = sms.begin();
	vs[cent] = 1;
	for(auto&i: adj[cent]) {
		if(vs[i.to]) continue;
		DNC(i.to, cum - (*it) + i.cto);
		it ++;
	}
}
int n, q;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i ++) {
    	int a, b, csf, cst;
    	cin >> a >> b >> csf >> cst;
    	swap(csf, cst);
    	adj[a].push_back({b, csf, cst});
    	adj[b].push_back({a, cst, csf});
    }
    for(auto&i: ans) i = INF;
    DNC(1, 0);
	for(int i = 2; i <= n; i ++) {
		ans[i] = min(ans[i], ans[i-1]);
	}
	cin >> q;
	while(q--) {
		int i;
		cin >> i;
		cout << ans[i] << "\n";
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44