Submission #552769

#	Time	Username	Problem	Language	Result	Execution time	Memory
552769		QwertyPi	Road Closures (APIO21_roads)	C++14	100 / 100	368 ms	53580 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<pair<int, int>>> G(100000);
vector<vector<int>> H(100000);

int w[100000], par[100000], dep[100000];
void dfs_build(int v, int p = -1, int depth = 0){
	dep[v] = depth;
	for(auto i : G[v]){
		if(i.first != p){
			dfs_build(i.first, v, depth + 1);
			w[i.first] = i.second;
			par[i.first] = v;
		}
	}
}

int dp[100000][2];
int n;

vector<long long> had;
bool isHeavy[100000];
vector<pair<int, int>> deg;

// vector<vector<int>> store(100001);

bool visited[100000];

int d(int v, int u){
	if(v == -1 || u == -1) return (1LL << 60);
	return (dep[v] > dep[u]) ? w[v] : w[u];
}

struct item {
    int key, prior, cnt = 0, sum = 0;
    item * l, * r;
    item() { }
    item (int key, int prior) : key(key), prior(prior), cnt(1), sum(key), l(nullptr), r(nullptr) { }
};

typedef item * pitem;

int cnt (pitem t) {
    return t ? t->cnt : 0;
}

int sum (pitem t){
	return t ? t->sum : 0;
}

void upd_cnt (pitem t) {
    if (t) t->cnt = 1 + cnt(t->l) + cnt(t->r);
}

void upd_sum (pitem t) {
    if (t) t->sum = t->key + sum(t->l) + sum(t->r);
}

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        split (t->l, key, l, t->l),  r = t;
    else
        split (t->r, key, t->r, r),  l = t;
    upd_cnt(t);
    upd_sum(t);
}

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (it->key < t->key ? t->l : t->r, it);
    upd_cnt(t);
    upd_sum(t);
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt(t);
    upd_sum(t);
}

void erase (pitem & t, int key) {
    if (t->key == key) {
        pitem th = t;
        merge (t, t->l, t->r);
        delete th;
    }
    else
        erase (key < t->key ? t->l : t->r, key);
    upd_cnt(t);
    upd_sum(t);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

int query(pitem & t, int k){
	if(!t || k == 0) return 0;
	if(cnt(t) == k) return t->sum;
	int res = 0;
	if(k <= cnt(t->l)) return query(t->l, k);
	if(cnt(t->l) + 1 <= k){
		res += sum(t->l);
		res += t->key;
		res += query(t->r, k - (cnt(t->l) + 1));
	}
	return res;
}

pitem store[100001];

void dfs(int v, int p = -1, int k = -1){
	visited[v] = true;
	vector<int> val;
	int ans = 0;
	int cnt = 0;
	
	for(auto i : H[v]){
		if(i != p){
			dfs(i, v, k);
			if(dp[i][0] <= dp[i][1]){
				ans += dp[i][0];
				cnt++;
				continue;
			}else{
				ans += dp[i][1];
				val.push_back(dp[i][0] - dp[i][1]);
			}
			
		}
	}
	
	for(auto i : val){
		pitem pi = new item(i, rng());
		insert(store[v], pi);
	}
	{
		int res = ans, to_del = max(0LL, (int) (G[v].size() - 1) - (k - 1) - cnt + 1);
		res += query(store[v], to_del);
		dp[v][1] = res;
	}
	{
		int res = ans + d(v, p), to_del = max(0LL, (int) (G[v].size() - 1) - (k) - cnt + 1);
		res += query(store[v], to_del);
		dp[v][0] = res;
	}
	for(auto i : val){
		erase(store[v], i);
	}
}

void migrate(int u, int v){ // u to v
	int weight = (dep[u] > dep[v] ? w[u] : w[v]);
	pitem pi = new item(weight, rng());
	insert(store[u], pi);
}

set<pair<int, int>> E;

void del_e(int u, int v){
	if(u > v) swap(u, v);
	E.erase({u, v});
}

void del(int v){
	for(auto i : G[v]){
		if(isHeavy[i.first]){
			migrate(i.first, v);
			del_e(i.first, v);
		}
	}
}

vector<long long> minimum_closure_costs(int32_t N, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
	for(int i = 0; i < N; i++){
		store[i] = new item(0, rng());
	}
	n = N;
	had.resize(N);
	for(int i = 0; i < N - 1; i++){
		if(U[i] > V[i]) swap(U[i], V[i]);
		G[U[i]].push_back({V[i], W[i]});
		G[V[i]].push_back({U[i], W[i]});
		E.insert({U[i], V[i]});
	}
	for(int i = 0; i < N; i++){
		deg.push_back({G[i].size(), i});
	}
	sort(deg.begin(), deg.end());
	int idx = 0;
	dfs_build(0);
	w[0] = (1LL << 60);
	fill(isHeavy, isHeavy + N, 1);
	for(int k = 0; k < N; k++){
		while(idx < N && deg[idx].first <= k){
			del(deg[idx].second);
			isHeavy[deg[idx].second] = false;
			idx++;
		}
		
		for(int i = idx; i < N; i++) visited[deg[i].second] = false;
		for(int i = idx; i < N; i++){
			H[deg[i].second].clear();
		}
		for(auto i : E){
			H[i.first].push_back(i.second);
			H[i.second].push_back(i.first);
		}
		for(int i = idx; i < N; i++){
			int v = deg[i].second;
			if(!visited[v]){
				dfs(v, -1, k);
				had[k] += min(dp[v][0], dp[v][1]);
			}
		}
//		cout << "FOR " << k << ": " << endl; 
//		for(int i = 0; i < n; i++){
//			cout << dp[i][0] << ' ' << dp[i][1] << endl;
//		}
	}
	return had;
}

• 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