Submission #1869785

---

Source Code Expand

//while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

const int nax=1000*10007;
using ll=long long;

int n;
vector < pair<int,ll> > graf[nax];

ll tab[nax];

ll wyn;


int bylcen[nax];

vector <int> spo;
int roz[nax];
int maxroz[nax];

vector < pair <int,ll> > ter;

vector < pair <ll , pair <int,int> > > kra;

int oj[nax];

int fin(int v)
{
	if (v!=oj[v])
		oj[v]=fin(oj[v]);
	return oj[v];
}

bool mniej(pair <int,ll> a, pair <int,ll> b)
{
	return a.second<b.second;
}

void dfs1(int v, int oj)
{
	roz[v]=1;
	maxroz[v]=0;
	spo.push_back(v);
	for (auto i : graf[v])
	{
		if(i.first==oj || bylcen[i.first])
			continue;
		dfs1(i.first, v);
		roz[v]+=roz[i.first];
		maxroz[v]=max(maxroz[v], roz[i.first]);
	}
}

void dfs2(int v, int oj, ll odl)
{
	ter.push_back({v, odl+tab[v]});
	for (auto i : graf[v])
	{
		if(i.first==oj || bylcen[i.first])
			continue;
		dfs2(i.first, v, odl+i.second);
	}
}

void szuk(int v)
{
	if (bylcen[v])
		return;
	spo.clear();
	dfs1(v, 0);
	
	int c=-1;
	int ss=spo.size();
	for (int i : spo)
		if (2*maxroz[i]<=ss && 2*(ss-roz[i])<=ss)
			c=i;
	
	bylcen[c]=1;
	
	ter.clear();
	dfs2(c, 0, 0LL);
	
	sort(ter.begin(), ter.end(), mniej);
	
	for (auto i : ter)
		kra.push_back({i.second+ter[0].second, {i.first, ter[0].first}});
	
	for (auto i : graf[c])
		szuk(i.first);
}

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
		scanf("%lld", &tab[i]);
	for (int i=1; i<n; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		graf[a].push_back({b, c});
		graf[b].push_back({a, c});
	}
	szuk(1);
	
	for (int i=1; i<=n; i++)
		oj[i]=i;
	
	sort(kra.begin(), kra.end());
	
	for (auto i : kra)
	{
		int x=fin(i.second.first);
		int y=fin(i.second.second);
		if (x!=y)
		{
			oj[x]=y;
			wyn+=i.first;
		}
	}
	
	printf("%lld\n", wyn);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:134:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:136:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &tab[i]);
                         ^
./Main.cpp:140:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
                              ^

Judge Result