제출 #726031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726031		SanguineChameleon	도로 폐쇄 (APIO21_roads)	C++17	31 / 100	2072 ms	44492 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;

struct segtree {
	int N, rem, node_id;
	vector<int> val;

	void init(int _node_id, vector<pair<int, int>> &pre_adj) {
		node_id = _node_id;
		N = pre_adj.size();
		rem = N;
		val.resize(N + 1);
		for (int i = 1; i <= N; i++) {
			val[i] = pre_adj[i - 1].first;
		}
		//build(1, 1, N);
	}

	void update(int pos) {
		pos++;
		val[pos] = 0;
		rem--;
	}

	long long get(int x) {
		x = max(x, 0);
		if (x == 0) {
			return 0;
		}
		if (x > rem) {
			return inf;
		}
		long long res = 0;
		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			if (val[i]) {
				res += val[i];
				cnt++;
				if (cnt == x) {
					break;
				}
			}
		}
		return res;
	}
};

vector<pair<int, int>> adj[maxN];
vector<pair<int, int>> pre_adj[maxN];
segtree tree[maxN];
vector<int> bucket[maxN];
int deg[maxN];
bool is_bad[maxN];
bool flag[maxN];
long long dp[maxN][2];
int K;

void dfs(int u, int par) {
	flag[u] = true;
	dp[u][0] = inf;
	dp[u][1] = inf;
	long long sum = 0;
	vector<long long> cost;
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (v == par) {
			continue;
		}
		dfs(v, u);
		sum += dp[v][1];
		cost.push_back(dp[v][0] + w - dp[v][1]);
	}
	sort(cost.begin(), cost.end());
	int cnt = deg[u] - (par != -1);
	for (int i = 0; i < 2; i++) {
		dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
	}
	for (auto w: cost) {
		sum += w;
		cnt--;
		for (int i = 0; i < 2; i++) {
			dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
		}
	}
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	vector<long long> res(N);
	for (int i = 0; i < N - 1; i++) {
		res[0] += W[i];
		pre_adj[U[i]].push_back({W[i], V[i]});
		pre_adj[V[i]].push_back({W[i], U[i]});
		deg[U[i]]++;
		deg[V[i]]++;
	}
	for (int i = 0; i < N; i++) {
		sort(pre_adj[i].begin(), pre_adj[i].end());
		tree[i].init(i, pre_adj[i]);
		bucket[deg[i]].push_back(i);
	}
	vector<int> bad;
	for (K = N - 1; K >= 1; K--) {
		for (auto u: bad) {
			flag[u] = false;
		}
		for (auto u: bad) {
			if (!flag[u]) {
				dfs(u, -1);
				res[K] += dp[u][0];
			}
		}
		for (auto u: bucket[K]) {
			for (auto e: pre_adj[u]) {
				int v = e.second;
				int w = e.first;
				if (is_bad[v]) {
					adj[u].push_back({v, w});
					adj[v].push_back({u, w});
					tree[u].update(lower_bound(pre_adj[u].begin(), pre_adj[u].end(), make_pair(w, v)) - pre_adj[u].begin());
					tree[v].update(lower_bound(pre_adj[v].begin(), pre_adj[v].end(), make_pair(w, u)) - pre_adj[v].begin());
				}
			}
			bad.push_back(u);
			is_bad[u] = true;
		}
	}
	return res;
}

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