Submission #1869788


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=200*1007;
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);
		//a=i;
		//b=i+1;
		//c=1;
		
		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

Submission Time
Task J - Tree MST
User Stonefeang
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 3090 Byte
Status AC
Exec Time 901 ms
Memory 104160 KB

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

Set Name sample All
Score / Max Score 0 / 0 1900 / 1900
Status
AC × 3
AC × 96
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt, 01-56.txt, 01-57.txt, 01-58.txt, 01-59.txt, 01-60.txt, 01-61.txt, 01-62.txt, 01-63.txt, 01-64.txt, 01-65.txt, 01-66.txt, 01-67.txt, 01-68.txt, 01-69.txt, 01-70.txt, 01-71.txt, 01-72.txt, 01-73.txt, 01-74.txt, 01-75.txt, 01-76.txt, 01-77.txt, 01-78.txt, 01-79.txt, 01-80.txt, 01-81.txt, 01-82.txt, 01-83.txt, 01-84.txt, 01-85.txt, 01-86.txt, 01-87.txt, 01-88.txt, 01-89.txt, 01-90.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 7680 KB
01-02.txt AC 3 ms 7680 KB
01-03.txt AC 3 ms 7680 KB
01-04.txt AC 26 ms 10676 KB
01-05.txt AC 750 ms 90464 KB
01-06.txt AC 750 ms 89056 KB
01-07.txt AC 741 ms 89440 KB
01-08.txt AC 753 ms 89440 KB
01-09.txt AC 699 ms 90976 KB
01-10.txt AC 732 ms 91232 KB
01-11.txt AC 737 ms 91360 KB
01-12.txt AC 732 ms 91232 KB
01-13.txt AC 736 ms 89056 KB
01-14.txt AC 749 ms 89952 KB
01-15.txt AC 749 ms 89440 KB
01-16.txt AC 743 ms 89056 KB
01-17.txt AC 737 ms 91616 KB
01-18.txt AC 714 ms 89696 KB
01-19.txt AC 712 ms 89696 KB
01-20.txt AC 781 ms 90464 KB
01-21.txt AC 773 ms 91488 KB
01-22.txt AC 777 ms 90592 KB
01-23.txt AC 783 ms 92640 KB
01-24.txt AC 772 ms 92512 KB
01-25.txt AC 792 ms 92000 KB
01-26.txt AC 780 ms 92256 KB
01-27.txt AC 784 ms 91488 KB
01-28.txt AC 789 ms 90968 KB
01-29.txt AC 790 ms 90708 KB
01-30.txt AC 268 ms 41576 KB
01-31.txt AC 278 ms 40940 KB
01-32.txt AC 269 ms 41324 KB
01-33.txt AC 281 ms 40808 KB
01-34.txt AC 280 ms 42728 KB
01-35.txt AC 900 ms 102872 KB
01-36.txt AC 901 ms 102624 KB
01-37.txt AC 886 ms 101600 KB
01-38.txt AC 883 ms 104040 KB
01-39.txt AC 866 ms 101728 KB
01-40.txt AC 866 ms 103392 KB
01-41.txt AC 183 ms 35948 KB
01-42.txt AC 192 ms 36844 KB
01-43.txt AC 187 ms 34796 KB
01-44.txt AC 183 ms 38124 KB
01-45.txt AC 779 ms 92128 KB
01-46.txt AC 807 ms 90976 KB
01-47.txt AC 837 ms 92000 KB
01-48.txt AC 889 ms 101576 KB
01-49.txt AC 867 ms 101592 KB
01-50.txt AC 872 ms 102496 KB
01-51.txt AC 876 ms 101472 KB
01-52.txt AC 859 ms 102888 KB
01-53.txt AC 865 ms 104160 KB
01-54.txt AC 861 ms 102240 KB
01-55.txt AC 660 ms 89188 KB
01-56.txt AC 653 ms 89444 KB
01-57.txt AC 614 ms 89312 KB
01-58.txt AC 719 ms 90852 KB
01-59.txt AC 703 ms 90720 KB
01-60.txt AC 684 ms 89312 KB
01-61.txt AC 627 ms 90084 KB
01-62.txt AC 639 ms 90848 KB
01-63.txt AC 637 ms 90084 KB
01-64.txt AC 709 ms 90596 KB
01-65.txt AC 716 ms 92512 KB
01-66.txt AC 732 ms 91232 KB
01-67.txt AC 612 ms 90212 KB
01-68.txt AC 636 ms 90336 KB
01-69.txt AC 652 ms 88676 KB
01-70.txt AC 691 ms 91236 KB
01-71.txt AC 695 ms 91492 KB
01-72.txt AC 697 ms 92000 KB
01-73.txt AC 563 ms 88544 KB
01-74.txt AC 549 ms 88544 KB
01-75.txt AC 538 ms 90596 KB
01-76.txt AC 605 ms 89188 KB
01-77.txt AC 638 ms 88672 KB
01-78.txt AC 616 ms 89316 KB
01-79.txt AC 551 ms 90592 KB
01-80.txt AC 578 ms 91740 KB
01-81.txt AC 586 ms 88928 KB
01-82.txt AC 632 ms 90980 KB
01-83.txt AC 653 ms 90720 KB
01-84.txt AC 622 ms 90468 KB
01-85.txt AC 562 ms 89188 KB
01-86.txt AC 568 ms 89184 KB
01-87.txt AC 566 ms 89828 KB
01-88.txt AC 655 ms 94176 KB
01-89.txt AC 630 ms 90932 KB
01-90.txt AC 648 ms 91108 KB
sample-01.txt AC 3 ms 7680 KB
sample-02.txt AC 3 ms 7680 KB
sample-03.txt AC 3 ms 7680 KB