Submission #586760

#	Time	Username	Problem	Language	Result	Execution time	Memory
586760		1ne	Toll (APIO13_toll)	C++14	16 / 100	0 ms	212 KiB

toll

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,cost;
};
struct DSU{
	vector<long long>parent,sz;
	//vector<pair<long long,long long>>ops;
	vector<long long>maxxy;
	set<pair<long long,long long>>new_edge;
	vector<vector<pair<long long,long long>>>adj;
	vector<vector<long long>>comp;
	void build(long long n){
		parent.resize(n);
		sz.resize(n);
		adj.resize(n);
		comp.resize(n);
		for (long long i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
			comp[i].push_back(i);
		}
	}
	void add_edge(long long u,long long v){
		new_edge.insert({max(u,v),min(u,v)});
	}
	long long findsets(long long v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(long long a,long long b,long long cost){
		long long u = findsets(a);
		long long v = findsets(b);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		pair<long long,long long>pos ={-1,-1};
		for (auto x:comp[u]){
			for (auto y:comp[v]){
				if (new_edge.find({max(x,y),min(x,y)})!=new_edge.end()){
					pos ={x,y};
					new_edge.erase({max(x,y),min(x,y)});
				}
			}
		}
		if (pos.first!=-1){
			adj[pos.first].push_back({pos.second,cost});
			adj[pos.second].push_back({pos.first,cost});
		}
		else{
			adj[a].push_back({b,0});
			adj[b].push_back({a,0});
		}
		//ops.push_back({v,parent[v]});
		parent[v] = u;
		//ops.push_back({~u,sz[u]});
		sz[u]+=sz[v];
		comp[u].insert(comp[u].end(),comp[v].begin(),comp[v].end());
		comp[v].clear();
		return true;
	}
	/*void roll_back(long long v){
		while((long long)ops.size() > v){
			long long i = ops.back().first;
			long long j = ops.back().second;
			ops.pop_back();
			if (i >= 0){
				parent[i] = j;
			}
			else{
				sz[~i] = j;
			}
		}
	}
	*/
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,m,k;cin>>n>>m>>k;
	vector<node>edge(m);
	for (long long i = 0;i<m;++i){
		long long x,y,cost;
		cin>>x>>y>>cost;
		--x;
		--y;
		edge.push_back({x,y,cost});
	}
	sort(edge.begin(),edge.end(),[&](auto x,auto y){
		return x.cost < y.cost;
	});
	DSU st;
	st.build(n);
	for (long long i = 0;i<k;++i){
		long long x,y;cin>>x>>y;
		--x;
		--y;
		st.add_edge(x,y);
	}
	vector<long long>p(n);
	for (long long i = 0;i<n;++i)cin>>p[i];
	for (auto x:edge){
		st.unionset(x.x,x.y,x.cost);
	}
	function<long long(long long,long long,long long)>dfs = [&](long long u,long long par,long long cost){
		long long ans = cost * p[u];
		for (auto x:st.adj[u]){
			if (x.first!=par){
				ans+=dfs(x.first,u,cost + x.second);
			}
		}
		return ans;
	};
	long long ans = dfs(0,-1,0);
	cout<<ans<<'\n';
	return 0;
}
/*
5 5 1
3 5 2 
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

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