Submission #885525

#	Time	Username	Problem	Language	Result	Execution time	Memory
885525		NK_	Designated Cities (JOI19_designated_cities)	C++17	13 / 100	210 ms	45244 KiB

designated_cities

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

#define f first
#define s second
#define mp make_pair

#define pb push_back

using ll = long long;
using pi = pair<int, int>;

template<class T> using V = vector<T>;
using vl = V<ll>;
using vpi = V<pi>;
using vi = V<int>;

using E = array<ll, 3>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N; cin >> N;

	V<V<E>> adj(N); vi deg(N); ll W = 0;
	for(int i = 0; i < N-1; i++) {
		int u, v, w, wi; cin >> u >> v >> w >> wi; --u, --v;
		adj[u].pb({v, w, wi});
		adj[v].pb({u, wi, w});
		deg[u]++, deg[v]++;
	}

	vl F(N); 
	function<void(int, int)> dfs = [&](int u, int p) {
		for(auto& e : adj[u]) {
			auto [v, tw, fw] = e; if (v == p) continue;
			W += tw; F[v] = F[u] + fw - tw;
			dfs(v, u);
		}
	};

	dfs(0, -1);	

	vl ans(N+1); ans[1] = W + *min_element(begin(F), end(F));

	vi dead(N); auto get = [&](int x) {
		for(auto& e : adj[x]) {
			if (!dead[e[0]]) return mp(e[2], e[0]);
		}

		return mp(-1LL, -1LL);
	};

	priority_queue<pi, vpi, greater<pi>> q; 
	for(int i = 0; i < N; i++) if (deg[i] == 1) {
		q.push(mp(get(i).f, i));
	}

	while(sz(q) > 2) {
		int u, w; tie(w, u) = q.top(); q.pop();
		// cout << u << " " << w << endl;

		dead[u] = 1;
		int p = get(u).s; deg[p]--;

		if (deg[p] == 1) q.push(mp(get(p).f + w, p));
		else {
			// cout << sz(q) << " " << w << endl;
			ans[sz(q)] = ans[sz(q) + 1] + w;
			// cout << ans[sz(q)] << " <= " << ans[sz(q) + 1] << endl;
		}
	}	

	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int e; cin >> e;
		cout << ans[e] << nl;
	}

	exit(0-0);
}

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