oj.uz

Submission #64438

# Submission time Handle Problem Language Result Execution time Memory
64438 2018-08-04T13:22:38 Z zetapi Cities (BOI16_cities) C++14
0 / 100
 316 ms 37636 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23800 KB Output is correct
2 Correct 25 ms 24036 KB Output is correct
3 Incorrect 24 ms 24036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 37388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 37388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 292 ms 37632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 37636 KB Output isn't correct
2 Halted 0 ms 0 KB -