Submission #263089

#	Time	Username	Problem	Language	Result	Execution time	Memory
263089		user202729	Toll (APIO13_toll)	C++17	78 / 100	2572 ms	22000 KiB

toll

// 2
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>

struct Dsu{ // with union by rank
	std::vector<int> data;
	Dsu(int number): data(number, -1){}
	void reset(){std::fill(begin(data), end(data), -1);}
	bool isRoot(int node)const{return data[node]<0;}
	int root(int node){return isRoot(node) ? node: data[node]=root(data[node]);}
	bool join(int first, int sec){
		first=root(first); sec=root(sec); if(first==sec) return false;
		if(data[first]<data[sec]) std::swap(first, sec);
		else if(data[first]==data[sec]) --data[sec];
		data[first]=sec;
		return true;
	}
};

struct Edge{int node, value;};
std::vector<std::vector<Edge>> add;

std::vector<int64_t> numPeople;

struct Info{
	int par;
	int depth;
};
std::vector<Info> info;
std::vector<int64_t> totalPeople;
template<bool computeTotalPeople=false> void work(int node, int par, int depth){
	info[node]={par, depth};
	if(computeTotalPeople)
		totalPeople[node]=numPeople[node];
	for(auto [other,_]: add[node]) {
		assert(other!=par);
		add[other].erase(std::find_if(begin(add[other]), end(add[other]), [&](Edge edge){return edge.node==node;}));
		work<computeTotalPeople>(other, node, depth+1);
		if(computeTotalPeople)
			totalPeople[node]+=totalPeople[other];
	}
}
std::vector<char> special;

std::vector<std::vector<int>> jump;
void makeJump(){
	if(jump.empty()) jump.resize(1);
	jump[0].resize(info.size());
	std::transform(begin(info), end(info), jump[0].begin(),[&](Info it){return it.par;});
	for(int layer=0;; ++layer){
		auto const& a=jump[layer];
		std::vector<int> b;
		if((int)jump.size()>layer+1) b=std::move(jump[layer+1]);
		b=a;

		bool useful=false;
		for(auto& it: b) if(it>=0 and (it=a[it])>=0) useful=true;
		if(useful){
			if((int)jump.size()==layer+1) jump.emplace_back();
			jump[layer+1]=std::move(b);
		}else{
			jump.resize(layer+1);
			break;
		}
	}
}

std::vector<int> rootPath(int node){
	if(node==0) return {0};
	auto result=rootPath(info[node].par);
	result.push_back(node); return result;
}
int lcaNaive(int first, int sec){
	auto const a=rootPath(first), b=rootPath(sec);
	return std::mismatch(begin(a), end(a),begin(b), end(b)).first[-1];
}
int la(int node, int delta){
	for(; delta; delta&=delta-1)
		node=jump[__builtin_ctz(delta)][node];
	return node;
}
int lca_(int first, int sec){
	auto dfirst=info[first].depth, dsec=info[sec].depth;
	if(dfirst>dsec) { std::swap(first, sec); std::swap(dfirst, dsec); }
	sec=la(sec, dsec-dfirst); assert(info[sec].depth==dfirst);
	if(first==sec) return first;
	for(auto layer=(int)jump.size(); layer--;)
		if(jump[layer][first]!=jump[layer][sec]){first=jump[layer][first]; sec=jump[layer][sec];}
	assert(jump[0][first]==jump[0][sec]); return jump[0][first];
}
int lca(int first, int sec){
	assert(lca_(first, sec)==lcaNaive(first, sec));
	return lca_(first, sec);
}

std::vector<char> deleted;
void work2(int node){
	for(auto& [other, curValue]: add[node]) {
		assert(other!=info[node].par);
		work2(other);
		if(not special[other]){
			if(add[other].size()==0){
				deleted[other]=true;
				numPeople[node]+=numPeople[other];
				other=-1;
			}else if(add[other].size()==1){
				auto const old=other, next=add[other][0].node;
				if(curValue<add[other][0].value){
					// merge node and old
					numPeople[node]+=numPeople[old];
					curValue=add[old][0].value; other=next;
					add[old].clear();
					deleted[old]=true;
				}else{
					assert(curValue>add[other][0].value);
					// merge old and next
					numPeople[next]+=numPeople[old];
					other=next;
					add[old].clear();
					deleted[old]=true;
				}
			}
		}
	}
	add[node].erase(std::remove_if(begin(add[node]), end(add[node]),[&](Edge edge){ return edge.node<0; }), add[node].end());
}

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int numNode, numEdge, numAdd; std::cin>>numNode>>numEdge>>numAdd;
	struct Edge{
		int first, sec, value;
		bool operator<(Edge other) const{return value<other.value;}
	};
	std::vector<Edge> edges(numEdge);
	for(auto& [first, sec, value]: edges){std::cin>>first>>sec>>value;--first;--sec;}
	std::sort(begin(edges), end(edges));

	add.resize(numNode);
	{ // only keep spanning tree of existing edges -> add
		Dsu dsu(numNode);
		//auto out=edges.begin();
		int count{};
		for(auto it: edges){
			if(dsu.join(it.first, it.sec)){
				//*out++=it;
				add[it.first].push_back({it.sec, it.value});
				add[it.sec].push_back({it.first, it.value});
				++count;
			}
		}
		assert(count==numNode-1);
		//edges.erase(out, edges.end());
		edges.clear();
	}

	info.resize(numNode);
	work(0, -1, 0);

	std::vector<std::array<int, 2>> specialEdges(numAdd);
	special.resize(numNode);
	makeJump();
	for(auto& [first, sec]: specialEdges){
		std::cin>>first>>sec;--first;--sec;
		special[first]=special[sec]=special[lca(first, sec)]=true;
	}
	assert(std::cin);

	numPeople.resize(numNode); for(auto& it: numPeople) std::cin>>it;
	deleted.resize(numNode);
	work2(0);
	info.clear();

	{ // compress the remaining part
		edges.clear();
		std::vector<int> remap(numNode, -1);
		int count=0;
		std::vector<int64_t> newNumPeople;
		for(int node=0; node<numNode; ++node)
			if(deleted[node]) assert(add[node].empty());
			else {
				for(auto it: add[node]) assert(not deleted[it.node]);
				remap[node]=count++;
				newNumPeople.push_back(numPeople[node]);
			}

		assert(edges.empty());
		for(int node=0; node<numNode; ++node)
			if(not deleted[node]){
				for(auto it: add[node])
					edges.push_back({remap[node], remap[it.node], it.value});
			}

		for(auto& it: specialEdges) for(auto& it: it){
			it=remap[it];
			assert(it>=0);
		}

		std::sort(begin(edges), end(edges));

		add.clear();
		deleted.clear();
		numNode=count;
		numPeople=std::move(newNumPeople);
	}

	Dsu dsu(numNode);
	int64_t result{};
	std::vector<Edge> exclude;
	info.resize(numNode);
	totalPeople.resize(numNode);
	for(auto mask=1<<numAdd; --mask;){
		dsu.reset();
		add.clear(); add.resize(numNode);
		exclude.clear();
		for(int index=0; index<numAdd; ++index)
			if(mask>>index&1){
				auto [first, sec]=specialEdges[index];
				if(not dsu.join(first, sec))
					goto next_mask;
				add[first].push_back({sec, ~index});
				add[sec].push_back({first, ~index});
				assert(~index<0);
			}

		for(auto [first, sec, value]: edges){
			assert(value>=0);
			if(dsu.join(first, sec)){
				add[first].push_back({sec, value}); add[sec].push_back({first, value});
			}else{
				exclude.push_back({first, sec, value});
			}
		}

		work<true>(0, -1, 0);
		makeJump();

		{
			// compute maximum edge cost from exclusions
			std::vector<std::vector<int>> value(jump.size(), std::vector<int>(numNode, INT_MAX));
			for(auto [first, sec, curValue]: exclude){
				auto w=lca(first, sec);
				auto const fill=[&](int node, int length){
					for(; length; length&=length-1){
						auto const layer=__builtin_ctz(length);
						value[layer][node]=std::min(value[layer][node], curValue);
						node=jump[layer][node];
					}
					assert(node==w);
				};
				fill(first, info[first].depth-info[w].depth);
				fill(sec, info[sec].depth-info[w].depth);
			}
			for(auto layer=(int)jump.size(); --layer;)
				for(int node=0; node<numNode; ++node){
					auto const a=value[layer][node];
					auto& b=value[layer-1][node]; auto& c=value[layer-1][jump[layer-1][node]];
					b=std::min(b, a); c=std::min(c, a);
				}

			int64_t curResult{};
			for(int node=0; node<numNode; ++node)
				for(auto [other, curValue]: add[node]){
					if(curValue<0){
						assert(value[0][other]!=INT_MAX);
						curResult+=value[0][other]*totalPeople[other];
					}
				}
			result=std::max(result, curResult);
		}

next_mask:;
	}
	std::cout<<result<<'\n';
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:184:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  184 |     for(auto it: add[node]) assert(not deleted[it.node]);
      |              ^~

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 0 / 22