Submission #366067

#	Time	Username	Problem	Language	Result	Execution time	Memory
366067		mahmoudbadawy	Sjekira (COCI20_sjekira)	C++17	110 / 110	275 ms	10348 KiB

sjekira

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=1e5+5;

set< pair<int, pair<int,int> > > ss;
int uni[N],mx[N];
int n;

int uni_find(int x)
{
	return uni[x]=(uni[x]==x?x:uni_find(uni[x]));
}

int unio(int x,int y)
{
	x=uni_find(x); y=uni_find(y);
	if(x==y) return 0;
	uni[x]=y;
	mx[y]=max(mx[x],mx[y]);
	return 1;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		uni[i]=i;
		scanf("%d",&mx[i]);
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		ss.insert({mx[x]+mx[y],{x,y}});
	}
	long long ans=0;
	while(ss.size())
	{
		auto cur=*ss.begin(); ss.erase(ss.begin());
		int a=uni_find(cur.S.F),b=uni_find(cur.S.S);
		if(a==b) continue;
		if(mx[a]+mx[b]!=cur.F)
			ss.insert({mx[a]+mx[b],{cur.S.F,cur.S.S}});
		else
		{
			ans+=mx[a]+mx[b];
			unio(a,b);
		}
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
sjekira.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |   scanf("%d",&mx[i]);
      |   ~~~~~^~~~~~~~~~~~~
sjekira.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   scanf("%d %d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60