제출 #726036

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

roads

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

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

struct node {
	long long sum = 0;
	int cnt = 0;
};

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

	void build(int id, int lt, int rt) {
		if (lt == rt) {
			tr[id].sum = val[lt];
			tr[id].cnt = 1;
			return;
		}
		int mt = (lt + rt) / 2;
		build(id * 2, lt, mt);
		build(id * 2 + 1, mt + 1, rt);
		tr[id].sum = tr[id * 2].sum + tr[id * 2 + 1].sum;
		tr[id].cnt = tr[id * 2].cnt + tr[id * 2 + 1].cnt;
	}

	void init(int _node_id, vector<pair<int, int>> &pre_adj) {
		node_id = _node_id;
		N = pre_adj.size();
		tr.resize(N * 4 + 20);
		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 id, int lt, int rt, int pos) {
		if (lt == rt) {
			tr[id].sum = 0;
			tr[id].cnt = 0;
			return;
		}
		int mt = (lt + rt) / 2;
		if (pos <= mt) {
			update(id * 2, lt, mt, pos);
		}
		else {
			update(id * 2 + 1, mt + 1, rt, pos);
		}
		tr[id].sum = tr[id * 2].sum + tr[id * 2 + 1].sum;
		tr[id].cnt = tr[id * 2].cnt + tr[id * 2 + 1].cnt;
	}

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

	long long get(int id, int lt, int rt, int cnt) {
		if (lt == rt) {
			assert(cnt == 1);
			return tr[id].sum;
		}
		int mt = (lt + rt) / 2;
		if (tr[id * 2].cnt >= cnt) {
			return get(id * 2, lt, mt, cnt);
		}
		else {
			return tr[id * 2].sum + get(id * 2 + 1, mt + 1, rt, cnt - tr[id * 2].cnt);
		}
	}

	long long get(int cnt) {
		cnt = max(cnt, 0);
		if (cnt == 0) {
			return 0;
		}
		if (cnt > rem) {
			return inf;
		}
		return get(1, 1, N, cnt);
	}
};

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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22