Submission #1871763


Source Code Expand

#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;

const int N=100005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
template<class T>inline void read(T &x){
	x=0;char ch=getchar(),rev=0;
	while(ch>'9'||ch<'0') rev=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=rev?-x:x;
}
template<class T>inline void print(T x,const char c){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[10];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int n,vis[N],si[N];
ll res,mn;
vector<pii> g[N];
vi id;
inline int getroot(int x,int f){
	int tmp=0,ans=1,t=0;
	for(pii y:g[x]){
		if(y.FF==f) continue;
		t=getroot(y.FF,x);
		gmax(tmp,t);ans+=t;
	}
	gmax(tmp,n-ans);
	if(tmp<=n/2) id.pb(x);
	return ans;
}
inline void dfs2(int x,int f){
	si[x]=1;
	for(pii y:g[x]){
		if(y.FF==f) continue;
		dfs2(y.FF,x);si[x]+=si[y.FF];
	}
//	printf("%d %d\n",x,si[x]);
}
inline void dfs(int x,int f,ll l,bool isok){
	res+=l;
	if(isok) gmin(mn,l);
	for(auto y:g[x])
		if(y.FF!=f) dfs(y.FF,x,l+y.SS,isok);
}

ll calc(int id){
//	debug(id);
	res=0;mn=1ll<<60;
	dfs2(id,0);
//	debug(si[id]);
	bool isok=1;
	for(pii y:g[id]) if(si[y.FF]==(n+1)/2) isok=0;
	for(pii y:g[id])
		dfs(y.FF,id,y.SS,(si[y.FF]==(n+1)/2)||isok);
//	debug(mn);
//	debug(res*2-mn);
	return res*2-mn;
}

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		g[x].pb(mp(y,z));g[y].pb(mp(x,z));
	}
	getroot(1,0);
	ll mx=0;
	for(int i:id) gmax(mx,calc(i));
	cout<<mx<<endl;
	return 0;
}

Submission Info

Submission Time
Task D - Tree and Hamilton Path
User rqgao2014
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 2504 Byte
Status AC
Exec Time 73 ms
Memory 9088 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:97:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:99:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int x,y,z;scanf("%d%d%d",&x,&y,&z);
                                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 2
AC × 38
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2560 KB
sample_02.txt AC 2 ms 2560 KB
subtask_1_01.txt AC 2 ms 2560 KB
subtask_1_02.txt AC 52 ms 6144 KB
subtask_1_03.txt AC 32 ms 4480 KB
subtask_1_04.txt AC 56 ms 6528 KB
subtask_1_05.txt AC 37 ms 5248 KB
subtask_1_06.txt AC 22 ms 4348 KB
subtask_1_07.txt AC 25 ms 4352 KB
subtask_1_08.txt AC 33 ms 4608 KB
subtask_1_09.txt AC 19 ms 3840 KB
subtask_1_10.txt AC 8 ms 3328 KB
subtask_1_11.txt AC 15 ms 3840 KB
subtask_1_12.txt AC 58 ms 6656 KB
subtask_1_13.txt AC 68 ms 6656 KB
subtask_1_14.txt AC 58 ms 6656 KB
subtask_1_15.txt AC 68 ms 6656 KB
subtask_1_16.txt AC 58 ms 6656 KB
subtask_1_17.txt AC 68 ms 6656 KB
subtask_1_18.txt AC 58 ms 6656 KB
subtask_1_19.txt AC 68 ms 6656 KB
subtask_1_20.txt AC 68 ms 6656 KB
subtask_1_21.txt AC 68 ms 6656 KB
subtask_1_22.txt AC 68 ms 6656 KB
subtask_1_23.txt AC 72 ms 8448 KB
subtask_1_24.txt AC 73 ms 8960 KB
subtask_1_25.txt AC 59 ms 6656 KB
subtask_1_26.txt AC 60 ms 7424 KB
subtask_1_27.txt AC 71 ms 8704 KB
subtask_1_28.txt AC 58 ms 6656 KB
subtask_1_29.txt AC 71 ms 9088 KB
subtask_1_30.txt AC 71 ms 8320 KB
subtask_1_31.txt AC 50 ms 6648 KB
subtask_1_32.txt AC 50 ms 6648 KB
subtask_1_33.txt AC 29 ms 5624 KB
subtask_1_34.txt AC 39 ms 6900 KB