Submission #570314

#	Time	Username	Problem	Language	Result	Execution time	Memory
570314		grt	Road Closures (APIO21_roads)	C++17	0 / 100	2081 ms	9152 KiB

roads

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10;
int n;
vector<tuple<int,int,int>>edges;
int cnt[nax];
vi weak[nax];
bool taken[nax];


vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) {
	n = N;
	for(int i = 0; i < n - 1; ++i) {
		edges.emplace_back(W[i], U[i], V[i]);
	}
	sort(edges.begin(), edges.end());
	vector<ll>ans(n);
	for(int k = 0; k < n; ++k) {
		ll res = 0;
		for(auto [c, a, b] : edges) {
			cnt[a]++, cnt[b]++;
		}
		int id = 1;
		for(auto [c, a, b] : edges) {
			if(cnt[a] > k && cnt[b] > k) {
				cnt[a]--, cnt[b]--;
				res += c;
				taken[id] = true;
			} else if(cnt[a] > k) {
				cnt[a]--;
				weak[a].PB(c);
				taken[id] = true;
			} else if(cnt[b] > k) {
				cnt[b]--;
				weak[b].PB(c);
				taken[id] = true;
			}
			id++;
		}
		id = 1;
		for(auto [c, a, b] : edges) {
			if(!taken[id]) {
				if(!weak[a].empty() && !weak[b].empty() && weak[a].back() + weak[b].back() > c) {
					res += c;
					weak[a].pop_back();
					weak[b].pop_back();
				}
			}
			id++;
		}
		for(int i = 0; i < n; ++i) {
			cnt[i] = 0;
			for(int c : weak[i]) res += c;
			weak[i].clear();
			taken[i] = false;
		}
		ans[k] = res;
	}
	return ans;
}


//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cin >> n;
	//vi u(n-1), v(n-1), w(n-1);
	//for(int i = 0; i < n-1; ++i) cin >> u[i] >> v[i] >> w[i];
	//auto vec = minimum_closure_costs(n, u, v, w);
	//for(auto x : vec) cout << x << " ";
//}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22