Submission #486906

#	Time	Username	Problem	Language	Result	Execution time	Memory
486906		wwdd	Road Closures (APIO21_roads)	C++14	12 / 100	1938 ms	86640 KiB

roads

//oh god why
#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;

struct DS {
	ll tot, dif, uval;
	// least = best to edge
	bool operator<(const DS& ot) const {
		return dif > ot.dif;
	}
};
vector<pl> pe;
vector<vector<ii> > g;
// vertex, edge color
vector<map<int,vector<DS>>> dpt;
vector<map<int,int> > degr;
vi wex;
void dfb(int u, int p, int col, int st, int deg) {
	int kv = degr[u][col]-(1-st)-deg;
	int sus = 0;
	int kt = 0;
	for(const auto& eg: dpt[u][col]) {
		int v = eg.uval;
		if(kt < kv && eg.dif > 0) {
			dfb(v,u,col,0,deg);
			sus++;
		} else {
			wex[v] |= deg;
			dfb(v,u,col,1,deg);
		}
		kt++;
	}
	if(!st) {
		sus++;
	}
	if(sus < kt+1) {
		degr[u][col|deg] = degr[u][col]-sus;
	}
	if(sus > 0) {
		degr[u][col] = degr[u][col]-deg;
	}
}
void dfa(int u, int p, int deg) {
	for(int i=0;i<g[u].size();i++) {
		int v = g[u][i].first;
		if(v == p) {continue;}
		dfa(v,u,deg);
	}
	dpt[u][wex[u]];
	for(const auto& colp: dpt[u]) {
		int col = colp.first;
		auto& subs = dpt[u][col];
		sort(subs.begin(),subs.end());
		pl res = {0,pe[u].second};
		int kv = degr[u][col]-deg;
		int kt = 0;
		for(const auto& eg: subs) {
			res.first += eg.tot;
			res.second += eg.tot;
			if(kt < kv) {
				ll dv = max(eg.dif,0LL);
				res.first += dv;
				if(kt < kv-1) {
					res.second += dv;
				}
			}
			kt++;
		}
		if(u != p && col == wex[u]) {
			dpt[p][col].push_back({res.first,res.second-res.first,u});
		} else {
			dfb(u,p,col,1,deg);
		}
	}
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
		std::vector<int> V,
		std::vector<int> W) {
	ll sus = 0;
	pe.resize(N);
	g.resize(N);
	wex.resize(N);
	int M = U.size();
	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;
	}
	int h = 0;
	while(1<<h < N) {
		h++;
	}
	vi ord;
	{
		stack<ii> st;
		st.emplace(0,0);
		ord.push_back(0);
		while(!st.empty()) {
			int u = st.top().first;
			ord.push_back(u);
			int p = st.top().second;
			st.pop();
			for(int i=0;i<g[u].size();i++) {
				int v = g[u][i].first;
				if(v == p) {continue;}
				int c = g[u][i].second;
				st.emplace(v,u);
				pe[v] = {u,c};
			}
		}
	}
	degr.resize(N);
	for(int i=0;i<N;i++) {
		degr[i][0] = 1<<(h);
	}
	for(int db=h-1;db>=0;db--) {
		dpt.assign(N,map<int,vector<DS>>());
		dfa(0,0,1<<db);
	}
	vector<ll> ans(N);
	for(int i=1;i<N;i++) {
		ans[wex[i]+1] += pe[i].second;
	}
	for(int i=1;i<ans.size();i++) {
		ans[i] += ans[i-1];
	}
	for(int i=0;i<ans.size();i++) {
		ans[i] = sus-ans[i];
	}
	return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfa(int, int, int)':
roads.cpp:53: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]
   53 |  for(int i=0;i<g[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:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    for(int i=0;i<g[u].size();i++) {
      |                ~^~~~~~~~~~~~
roads.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |  for(int i=1;i<ans.size();i++) {
      |              ~^~~~~~~~~~~
roads.cpp:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |  for(int i=0;i<ans.size();i++) {
      |              ~^~~~~~~~~~~

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