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
2017-12-15 12:18:42+0900
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
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