Submission #487089

#	Time	Username	Problem	Language	Result	Execution time	Memory
487089		wwdd	Road Closures (APIO21_roads)	C++14	100 / 100	736 ms	518684 KiB

roads

//wtf is this
#include "roads.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
const ll INFL = 1e18;
const ll BIG = 1e10;

class ST {
	private:
	struct NO {
		NO *lf,*rt;
		ll su, kt;
		NO() {
			su = kt = 0;
			lf = rt = nullptr;
		}
		NO(ll val) {
			su = val;
			kt = 1;
			lf = rt = nullptr;
		}
	};
	ll get(NO* no, ll l, ll r, ll q) {
		if(no->kt < q) {
			return INFL;
		}
		if(q <= 0) {return 0;}
		if(l == r) {
			return l*q;
		}
		ll m = (l+r)/2;
		ll ans = 0;
		if(no->lf != nullptr) {
			if(no->lf->kt >= q) {
				return get(no->lf,l,m,q);
			} else {
				ans += no->lf->su;
				q -= no->lf->kt;
			}
		}
		if(no->rt != nullptr) {
			ans += get(no->rt,m+1,r,q);
		}
		return ans;
	}
	vector<NO*> st;
	ll subz,sukt;
	void ens(NO* no, ll l, ll r, ll val, ll num) {
		no->su += val*num;
		no->kt += num;
		if(l == r) {
			return;
		}
		ll m = (l+r)/2;
		if(val <= m) {
			if(no->lf == nullptr) {
				NO* nx = new NO();
				st.push_back(nx);
				no->lf = nx;
			}
			ens(no->lf,l,m,val,num);
		} else {
			if(no->rt == nullptr) {
				NO* nx = new NO();
				st.push_back(nx);
				no->rt = nx;
			}
			ens(no->rt,m+1,r,val,num);
		}
	}
	ll ls, rs;
	public:
	ST(ll ls_, ll rs_) {
		ls = ls_;
		rs = rs_;
		st.push_back(new NO());
		sukt = subz = 0;
	}
	ll get(ll q) {
		ll ad = subz;
		q -= sukt;
		return ad+get(st.front(),ls,rs,q);
	}
	void ens(ll val) {
		if(val < 0) {
			subz += val;
			sukt++;
		} else {
			ens(st.front(),ls,rs,val,1);
		}
	}
	void del(ll val) {
		if(val < 0) {
			subz -= val;
			sukt--;
		} else {
			ens(st.front(),ls,rs,val,-1);
		}
	}
};

vl degs;
vector<vector<ii>> h;
vector<ST> wos;
vl lov;
pl dfs(ll u, ll p, int deg) {
	lov[u] = deg;
	ll ad = 0;
	vector<pl> difs;
	ll rek = degs[u]-deg;
	for(int i=0;i<h[u].size();i++) {
		int v = h[u][i].first;
		ll c = h[u][i].second;
		if(v == p) {
			wos[u].del(c);
			difs.emplace_back(c,-INFL);
			continue;
		}
		pl res = dfs(v,u,deg);
		if(res.first >= INFL) {
			difs.emplace_back(c,-INFL);
			wos[u].del(c);
			rek--;
			ad += c+res.second;
		} else {
			difs.emplace_back(c,c+res.second-res.first);
			wos[u].del(c);
			wos[u].ens(c+res.second-res.first);
			ad += res.first;
		}
	}
	pl ans = {wos[u].get(rek)+ad,wos[u].get(rek-1)+ad};
	for(const auto& it: difs) {
		if(it.second > -INFL) {
			wos[u].del(it.second);
		}
		wos[u].ens(it.first);
	}
	return ans;
}
vector<vector<ii> > g;
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
		std::vector<int> V,
		std::vector<int> W) {
	ll sus = 0;
	int M = U.size();
	degs.assign(N,0);
	g.resize(N);
	for(int i=0;i<M;i++) {
		int u = U[i];
		int v = V[i];
		int c = W[i];
		g[u].emplace_back(v,c);
		g[v].emplace_back(u,c);
		sus += c;
		degs[u]++;
		degs[v]++;
	}
	vector<ii> ord;
	for(int i=0;i<N;i++) {
		ord.emplace_back(degs[i],i);
	}
	sort(ord.begin(),ord.end());
	vi rord(N);
	for(int i=0;i<ord.size();i++) {
		rord[ord[i].second] = i;
	}
	int pt = N-1;
	for(int i=0;i<N;i++) {
		wos.emplace_back(0,BIG);
	}
	for(int i=0;i<N;i++) {
		for(const auto& eg: g[i]) {
			int c = eg.second;
			wos[i].ens(c);
		}
	}
	h.resize(N);
	lov.assign(N,N);
	vector<ll> ans(N);
	for(int dv=N-1;dv>=1;dv--) {
		while(pt >= 0 && degs[ord[pt].second] > dv) {
			int u = ord[pt].second;
			for(const auto& eg: g[u]) {
				int v = eg.first;
				int c = eg.second;
				if(rord[v] > rord[u]) {
					h[u].emplace_back(v,c);
					h[v].emplace_back(u,c);
				}
			}
			pt--;
		}
		ll res = 0;
		for(int i=N-1;i>pt;i--) {
			int u = ord[i].second;
			if(lov[u] > dv) {
				res += dfs(u,u,dv).first;
			}
		}
		ans[dv] = res;
	}
	ans[0] = sus;
	return ans;
}

Compilation message (stderr)

roads.cpp: In function 'pl dfs(ll, ll, int)':
roads.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i=0;i<h[u].size();i++) {
      |              ~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:173:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |  for(int i=0;i<ord.size();i++) {
      |              ~^~~~~~~~~~~

• 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