Submission #64438

#	Time	Username	Problem	Language	Result	Execution time	Memory
64438		zetapi	Cities (BOI16_cities)	C++14	0 / 100	316 ms	37636 KiB

cities

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e6;

pair<int,pii> edge[MAX];

vector<pii> vec[MAX];

int N,K,M,res,arr[MAX],mark[MAX],height[MAX],Parent[MAX];
int par[MAX],ranks[MAX];

void init()
{
	for(int A=1;A<=N;A++)
	{
		par[A]=A;
		ranks[A]=0;
	}
	return ;
}

int root(int X)
{
	if(par[X]==X)
		return X;
	return par[X]=root(par[X]);
}

void unions(int X,int Y)
{
	int u=root(X),v=root(Y);
	if(ranks[u]>ranks[v])
		swap(u,v);
	par[u]=v;
	ranks[u]+=(ranks[u]==ranks[v]);
	return ;
}

void dfs(int node,int par,int h)
{
	height[node]=h;
	for(auto A:vec[node])
	{
		if(A.first==par)
			continue;
		Parent[A.first]=node;
		dfs(A.first,node,h+1);
	}
	return ;
}

void dfs(int node,int par)
{
	for(auto A:vec[node])
	{
		if(A.first==par)
			continue;
		if(mark[A.first])
			res+=A.second;
		dfs(A.first,node);
	}
	return ;
}

signed main()
{
	ios_base::sync_with_stdio(false);

	cin>>N>>K>>M;
	for(int A=1;A<=K;A++)
		cin>>arr[A];
	for(int A=1;A<=M;A++)
		cin>>edge[A].second.first>>edge[A].second.second>>edge[A].first;
	sort(edge+1,edge+M+1);
	init();
	for(int A=1;A<=M;A++)
	{
		if(root(edge[A].second.first)!=root(edge[A].second.second))
		{
			unions(edge[A].second.first,edge[A].second.second);
			vec[edge[A].second.first].pb(mp(edge[A].second.second,edge[A].first));
			vec[edge[A].second.second].pb(mp(edge[A].second.first,edge[A].first));
		}
	}
	dfs(1,0,0);
	int u,v;
	for(int A=1;A<=K;A++)
	{
		for(int B=A+1;B<=K;B++)
		{	
			u=arr[A];
			v=arr[B];
			if(height[u]>height[v])
				swap(u,v);
			while(height[v]>height[u])
			{
				mark[v]=1;
				v=Parent[v];
			}
			while(u!=v)
			{
				mark[u]=1;
				mark[v]=1;
				u=Parent[u];
				v=Parent[v];
			}
		}
	}
	dfs(1,0);
	cout<<res;
	return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26