제출 #567881

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

roads

#include "roads.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 2e9;
struct node{
	ll x, y, cnt, cc, sum;
	node *lx, *rx;
	
	node(int v) : x(v), cnt(1), cc(1), sum(v), lx(NULL), rx(NULL){
		y = uniform_int_distribution<int>(0, inf)(rng);
	}
};

struct RBST{
	void upd(node* a){
		a->cnt = a->cc, a->sum = a->x * a->cc;
		if(a->lx != NULL) a->cnt += a->lx->cnt, a->sum += a->lx->sum;
		if(a->rx != NULL) a->cnt += a->rx->cnt, a->sum += a->rx->sum;
	}
	node* merge(node* a, node* b){
		if(a == NULL) return b;
		if(b == NULL) return a;
		if(a->y > b->y){
			a->rx = merge(a->rx, b);
			upd(a);
			return a;
		} else {
			b->lx = merge(a, b->lx);
			upd(b);
			return b;
		}
	}
	
	ar<node*, 2> split(node* a, int v){
		if(a == NULL) return {NULL, NULL};
		if(v <= a->x){
			auto tt = split(a->lx, v);
			a->lx = tt[1];
			upd(a);
			return {tt[0], a};
		} else {
			auto tt = split(a->rx, v);
			a->rx = tt[0];
			upd(a);
			return {a, tt[1]};
		}
	}
	
	bool check(node*& root, int v){
		if(root == NULL) return false;
		if(root->x == v){
			root->cc++;
			upd(root);
			return true;
		} if(root->x < v) return check(root->lx, v);
		else return check(root->rx, v);
	}
	
	bool rcheck(node*& root, int v){
		if(root == NULL) return false;
		if(root->x == v){
			assert(root->cc > 0);
			root->cc--, upd(root);
			return true;
		} if(root->x < v) return rcheck(root->lx, v);
		else return rcheck(root->rx, v);
	}
	
	void insert(node*& root, int v){
		if(check(root, v)) return;
		node* tmp = new node(v);
		auto tt = split(root, v);
		root = merge(tt[0], merge(tmp, tt[1]));
	}
	
	void erase(node*& root, int v){
		assert(rcheck(root, v));
		//~ auto L = split(root, v);
		//~ auto R = split(L[1], v + 1);
		//~ assert(R[0] != NULL);
		//~ if(R[0] == NULL){
			//~ root = merge(L[0], R[1]);
			//~ return;
		//~ }
		//~ if(--R[0]->cc){
			//~ upd(R[0]);
			//~ root = merge(L[0], merge(R[0], R[1]));
		//~ } else {
			//~ root = merge(L[0], R[1]);
		//~ }
	}
	
	ll get(node* a, int v){
		if(v == 0 || a == NULL) return 0;
		if(a->lx != NULL && v < a->lx->cnt) return get(a->lx, v);
		ll res = 0;
		if(a->lx != NULL) res += a->lx->sum, v -= a->lx->cnt;
		if(v <= a->cc) return res + v * a->x;
		res += a->cc * a->x, v -= a->cc;
		return res + get(a->rx, v);
	}
}tree;

const int N = 1e5 + 5;
vector<int> edges[N];
vector<ar<ll, 2>> work[N];
int d[N], used[N], CUR;
ll dp[N][2], tot[N];
node* bad[N];
multiset<int> mm[N];

void dfs(int u, int p = -1){
	used[u] = 1;
	dp[u][0] = dp[u][1] = tot[u];
	vector<ll> tt;
	for(auto x : work[u]){
		if(x[0] == p) continue;
		tot[x[0]] -= x[1];
		dfs(x[0], u);
		tot[x[0]] += x[1];
		dp[u][0] += dp[x[0]][0], dp[u][1] += dp[x[0]][0];
		tt.push_back(dp[x[0]][1] - dp[x[0]][0] - x[1]);
	}
	
	sort(tt.begin(), tt.end());
	for(int t=0;t<2;t++){
		ll cur = dp[u][t];
		for(int j=0;j<=min((int)tt.size(), CUR - t);j++){
			int rem = CUR - t - j;
			dp[u][t] = min(dp[u][t], cur + tree.get(bad[u], rem));
			if(j < (int)tt.size()) cur += tt[j];
		}
	}
}

vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
	vector<int> p;
	p.push_back(n - 1);
	for(int i=0;i<n-1;i++){
		d[u[i]]++, d[v[i]]++;
		edges[u[i]].push_back(i);
		edges[v[i]].push_back(i);
		tree.insert(bad[u[i]], -w[i]);
		tree.insert(bad[v[i]], -w[i]);
		mm[v[i]].insert(-w[i]), mm[u[i]].insert(-w[i]);
		tot[v[i]] += w[i], tot[u[i]] += w[i];
		p.push_back(i);
	} 
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (d[i] > d[j]);
	});
	
	vector<ll> tt, res(n);
	auto add = [&](int a){
		tt.push_back(a);
		for(auto i : edges[a]){
			int x = u[i] ^ v[i] ^ a;
			//~ assert(mm[x].count(-w[i]));
			mm[x].erase(mm[x].find(-w[i]));
			tree.erase(bad[x], -w[i]);
			work[x].push_back({a, w[i]});
		}
	};
	
	int j = 0;
	for(int x=n-1;~x;x--){ CUR = x;
		while(j < n && d[p[j]] >= x){
			add(p[j]);
			j++;
		}
		
		for(auto u : tt){
			if(used[u]) continue;
			dfs(u);
			res[x] += dp[u][0];
		}
		
		for(auto x : tt) used[x] = 0;
	}
	
	return res;
}

/*

5
0 1 1
0 2 4
0 3 3
2 4 2

0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0

2 0 0 0 0
2 2 0 0 0

0 0 0 0 0
0 0 0 0 0

10 5 1 0 0
10 8 4 1 0

*/

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