제출 #1133822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133822		Math4Life2020	도로 폐쇄 (APIO21_roads)	C++20	36 / 100	2033 ms	40736 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

mt19937 gen;
const ll Nm = 1e5+5; ll N;
const ll K = 250; //sqrt(N)
ll ans[Nm];

vector<pii> adj[Nm];
vector<ll> fadj[Nm];
ll deg[Nm];
pii radj[Nm]; //{number, cost}
vector<ll> itpl; //inverse topological sort

ll dp0[Nm]; //no path up
ll dp1[Nm]; //path up

ll qsel(ll nv, vector<ll> v0) { //quickselect bottom nv elements
	if (nv==0) {
		return 0;
	}
	vector<ll> v1,v2; ll neq=0; //bottom, top, # equal
	ll s1=0,s2=0;
	ll x = v0[gen()%(v0.size())];
	for (ll y: v0) {
		if (y<x) {
			v1.push_back(y);
			s1+=y;
		} else if (y>x) {
			v2.push_back(y);
			s2+=y;
		} else {
			neq++;
		}
	}
	if ((v1.size()+neq)<=nv) {
		return (s1+x*neq+qsel(nv-v1.size()-neq,v2));
	} else if (v1.size()>nv) {
		return qsel(nv,v1);
	} else {
		return (s1+x*(nv-v1.size()));
	}
}

ll slvH(ll k) { //O(NlogN) independent of k
	for (ll i=(N-1);i>=0;i--) {
		ll x = itpl[i];
		vector<ll> vaug; //augment vector
		ll val0 = 0; //minimum value
		for (ll y: fadj[x]) {
			val0 += dp0[y];
			vaug.push_back(dp1[y]-dp0[y]);
		}
		//sort(vaug.begin(),vaug.end()); //can upgrade quicksort -> quickselect for true O(N)
		ll NDEL = max(0LL,deg[x]-k);
		dp0[x]=val0+qsel(NDEL,vaug);
		NDEL = max(0LL,deg[x]-k-1);
		dp1[x]=val0+radj[x].second+qsel(NDEL,vaug);
		if (x!=0) {
			dp0[x]=min(dp1[x],dp0[x]);
		}
	}
	return dp0[0];
}

bool isH[Nm]; //is heavy? (aka deg>=K)
ll degL[Nm]; //light degree
vector<ll> aggL[Nm]; //light aggregates (choose x edges -> give cost)
vector<ll> elemL[Nm];
vector<pii> adjH[Nm];
pii radjH[Nm]; //heavy radj
vector<ll> fadjH[Nm]; //heavy fadj
vector<bool> foundH;

// ll gcalc(ll ndel, vector<ll> vaug, ll x) {
// 	vector<ll> vnew = vaug;
// 	for (ll y: elemL[x]) {
// 		vnew.push_back(y);
// 	}
// 	sort(vnew.begin(),vnew.end());
// 	ll vnewv = 0;
// 	for (ll i=0;i<ndel;i++) {
// 		vnewv += vnew[i];
// 	}
// 	return vnewv;
// }

ll gcalc(ll ndel, vector<ll> vaug, ll x) {
	if (ndel==0) {return 0;}
	if (elemL[x].size()==0 || ((vaug.size()>=ndel)&&(vaug[ndel-1]<=elemL[x][0]))) {
		ll y = 0;
		for (ll i=0;i<ndel;i++) {
			y += vaug[i];
		}
		return y;
	}
	ll y=0; ll nfv=0; //total value, number from vaug
	while (nfv<vaug.size()) {
		if (nfv == ndel) {
			return y;
		}
		auto A0 = upper_bound(elemL[x].begin(),elemL[x].end(),vaug[nfv]);
		ll d0 = distance(elemL[x].begin(),A0); //# of elements <= vaug[nfv]
		if ((d0+nfv+1)<=ndel) {
			y += vaug[nfv];
			nfv++;
		} else {
			return (y+aggL[x][ndel-nfv]);
		}
	}
	return (aggL[x][ndel-nfv]+y);
}

ll slvL(ll k, vector<ll> rtpl /*reverse topological sort*/) { //O(SIZElogN) but need preprocessing -> only works for k>=K
	for (ll i=(rtpl.size()-1);i>=0;i--) {
		ll x = rtpl[i];
		vector<ll> vaug;
		ll val0 = 0;
		for (ll y: fadjH[x]) {
			val0 += dp0[y];
			vaug.push_back(dp1[y]-dp0[y]);
		}
		sort(vaug.begin(),vaug.end());
		dp0[x] = val0+gcalc(max(0LL,deg[x]-k),vaug,x);
		dp1[x] = val0+radjH[x].second+gcalc(max(0LL,deg[x]-k-1),vaug,x);
		if (i!=0) {
			dp0[x]=min(dp1[x],dp0[x]);
		}
	}
	return dp0[rtpl[0]];
}

vector<ll> minimum_closure_costs(int N1, vector<int> U, vector<int> V, vector<int> W) {
	gen = mt19937((long long) new char);
	N=N1;
	for (ll i=0;i<N;i++) {
		adj[i].clear();
		fadj[i].clear();
	}
	itpl.clear();
	ll sroad = 0;
	for (ll i=0;i<(N-1);i++) {
		adj[U[i]].push_back({V[i],W[i]});
		adj[V[i]].push_back({U[i],W[i]});
		sroad += W[i];
	}
	for (ll i=0;i<N;i++) {
		deg[i]=adj[i].size();
	}
	queue<ll> q0;
	q0.push(0); //root is 0
	radj[0]={-1,-1};
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		itpl.push_back(x);
		for (pii p0: adj[x]) {
			if (p0.first!=radj[x].first) {
				fadj[x].push_back(p0.first);
				radj[p0.first]={x,p0.second};
				q0.push(p0.first);
			}
		}
	}
	for (ll i=0;i<N;i++) {
		isH[i]=(deg[i]>=K);
		radjH[i]={-1LL,-1LL};
	}
	for (ll i=0;i<N;i++) {
		if (!isH[i]) {
			continue;
		}
		vector<ll> iadjL; //values
		for (pii p0: adj[i]) {
			ll x = p0.first;
			if (isH[x]) {
				adjH[i].push_back(p0);
			} else {
				iadjL.push_back(p0.second);
			}
		}
		degL[i]=iadjL.size();
		sort(iadjL.begin(),iadjL.end());
		elemL[i]=iadjL;
		aggL[i].push_back(0);
		ll cv = 0;
		for (ll x: iadjL) {
			cv += x;
			aggL[i].push_back(cv);
		}
	}
	foundH = vector<bool>(N,0);
	vector<vector<ll>> itplsH; //heavy inverse topological sort 

	for (ll i=0;i<N;i++) {
		if (!isH[i] || foundH[i]) {
			continue;
		}
		queue<ll> q1;
		q1.push(i);
		vector<ll> vtc;
		while (!q1.empty()) {
			ll x = q1.front(); q1.pop();
			foundH[x]=1;
			vtc.push_back(x);
			for (pii p0: adjH[x]) {
				if (p0.first!=radjH[x].first) {
					fadjH[x].push_back(p0.first);
					radjH[p0.first]={x,p0.second};
					q1.push(p0.first);
				}
			}
		}
		itplsH.push_back(vtc);
	}


	for (ll k=1;k<K;k++) {
		ans[k]=slvH(k);
	}
	for (ll k=K;k<N;k++) {
		ans[k]=0;
		for (auto A0: itplsH) {
			ans[k] += slvL(k,A0);
		}
	}
	ans[0]=sroad;
	vector<ll> ansF(N,0);
	for (ll i=0;i<N;i++) {
		ansF[i]=ans[i];
	}
	return ansF;
}

• Subtask 1: 5 / 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