Submission #2313133
Source Code Expand
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=200010; int tt,sum,rt,cnt,tp; bool vis[N]; int head[N],to[N*2],nxt[N*2],s[N*2],sz[N],Mx[N],a[N],pa[N]; struct Dat { int x,y;ll z; inline bool operator < (const Dat &A) const {return z<A.z;} } g[N],f[N*20],pre; inline int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*o; } inline void get_rt(int x,int fa) { sz[x]=1,Mx[x]=0; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(!vis[y]&&y!=fa) { get_rt(y,x),sz[x]+=sz[y]; Mx[x]=max(Mx[x],sz[y]); } } Mx[x]=max(Mx[x],sum-sz[x]); rt=(Mx[x]<Mx[rt]?x:rt); } inline void get_dep(int x,ll d,int fa) { g[++tp]=(Dat){x,0,d+a[x]}; pre=min(pre,g[tp]); for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=fa) get_dep(to[i],d+s[i],x); } inline void solve(int x) { vis[x]=1,tp=0,pre=(Dat){0,0,1LL<<60}; get_dep(x,0,0); for(int i=1;i<=tp;i++) f[++cnt]=(Dat){pre.x,g[i].x,pre.z+g[i].z}; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(!vis[y]) { sum=sz[y],rt=0; get_rt(y,x),solve(rt); } } } inline int find(int x) {return pa[x]==x?x:pa[x]=find(pa[x]);} int main() { int n; cin>>n; for(int i=1;i<=n;i++) a[i]=gi(),pa[i]=i; for(int i=1;i<n;i++) { int x=gi(),y=gi(),z=gi(); to[++tt]=y,nxt[tt]=head[x],s[tt]=z,head[x]=tt; to[++tt]=x,nxt[tt]=head[y],s[tt]=z,head[y]=tt; } Mx[0]=sum=n,get_rt(1,0); solve(rt); sort(f+1,f+1+cnt); ll ans=0; for(int i=1;i<=cnt;i++) { int x=find(f[i].x),y=find(f[i].y); if(x!=y) pa[x]=y,ans+=f[i].z; } cout<<ans; return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - Tree MST |
User | Anson |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 1902 Byte |
Status | AC |
Exec Time | 623 ms |
Memory | 71296 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1900 / 1900 | ||||
Status |
|
|
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 | 10496 KB |
01-02.txt | AC | 3 ms | 10496 KB |
01-03.txt | AC | 3 ms | 10496 KB |
01-04.txt | AC | 20 ms | 12032 KB |
01-05.txt | AC | 581 ms | 54144 KB |
01-06.txt | AC | 520 ms | 56192 KB |
01-07.txt | AC | 528 ms | 54144 KB |
01-08.txt | AC | 542 ms | 54144 KB |
01-09.txt | AC | 538 ms | 54144 KB |
01-10.txt | AC | 551 ms | 54144 KB |
01-11.txt | AC | 562 ms | 54144 KB |
01-12.txt | AC | 570 ms | 54144 KB |
01-13.txt | AC | 573 ms | 54144 KB |
01-14.txt | AC | 592 ms | 56192 KB |
01-15.txt | AC | 593 ms | 56192 KB |
01-16.txt | AC | 583 ms | 56192 KB |
01-17.txt | AC | 582 ms | 54144 KB |
01-18.txt | AC | 572 ms | 54144 KB |
01-19.txt | AC | 560 ms | 54144 KB |
01-20.txt | AC | 524 ms | 60800 KB |
01-21.txt | AC | 520 ms | 60800 KB |
01-22.txt | AC | 534 ms | 60800 KB |
01-23.txt | AC | 548 ms | 60800 KB |
01-24.txt | AC | 564 ms | 60800 KB |
01-25.txt | AC | 572 ms | 60800 KB |
01-26.txt | AC | 584 ms | 60800 KB |
01-27.txt | AC | 605 ms | 60800 KB |
01-28.txt | AC | 604 ms | 60800 KB |
01-29.txt | AC | 605 ms | 60800 KB |
01-30.txt | AC | 177 ms | 25472 KB |
01-31.txt | AC | 184 ms | 25472 KB |
01-32.txt | AC | 183 ms | 25472 KB |
01-33.txt | AC | 177 ms | 25472 KB |
01-34.txt | AC | 171 ms | 25472 KB |
01-35.txt | AC | 523 ms | 71296 KB |
01-36.txt | AC | 545 ms | 71296 KB |
01-37.txt | AC | 556 ms | 71296 KB |
01-38.txt | AC | 581 ms | 71296 KB |
01-39.txt | AC | 601 ms | 71296 KB |
01-40.txt | AC | 623 ms | 71296 KB |
01-41.txt | AC | 101 ms | 21376 KB |
01-42.txt | AC | 103 ms | 21376 KB |
01-43.txt | AC | 104 ms | 21376 KB |
01-44.txt | AC | 104 ms | 21376 KB |
01-45.txt | AC | 562 ms | 58368 KB |
01-46.txt | AC | 555 ms | 58368 KB |
01-47.txt | AC | 559 ms | 58368 KB |
01-48.txt | AC | 470 ms | 71296 KB |
01-49.txt | AC | 464 ms | 71296 KB |
01-50.txt | AC | 469 ms | 71296 KB |
01-51.txt | AC | 455 ms | 71296 KB |
01-52.txt | AC | 498 ms | 71296 KB |
01-53.txt | AC | 496 ms | 71296 KB |
01-54.txt | AC | 487 ms | 71296 KB |
01-55.txt | AC | 427 ms | 56320 KB |
01-56.txt | AC | 421 ms | 56320 KB |
01-57.txt | AC | 385 ms | 54144 KB |
01-58.txt | AC | 441 ms | 60288 KB |
01-59.txt | AC | 451 ms | 60416 KB |
01-60.txt | AC | 386 ms | 62464 KB |
01-61.txt | AC | 394 ms | 56320 KB |
01-62.txt | AC | 412 ms | 56192 KB |
01-63.txt | AC | 394 ms | 54272 KB |
01-64.txt | AC | 464 ms | 60928 KB |
01-65.txt | AC | 458 ms | 61056 KB |
01-66.txt | AC | 462 ms | 61184 KB |
01-67.txt | AC | 412 ms | 56320 KB |
01-68.txt | AC | 418 ms | 56320 KB |
01-69.txt | AC | 412 ms | 56320 KB |
01-70.txt | AC | 412 ms | 63232 KB |
01-71.txt | AC | 416 ms | 63232 KB |
01-72.txt | AC | 400 ms | 63488 KB |
01-73.txt | AC | 354 ms | 56320 KB |
01-74.txt | AC | 349 ms | 56320 KB |
01-75.txt | AC | 340 ms | 56320 KB |
01-76.txt | AC | 375 ms | 62464 KB |
01-77.txt | AC | 388 ms | 60416 KB |
01-78.txt | AC | 372 ms | 60416 KB |
01-79.txt | AC | 343 ms | 56320 KB |
01-80.txt | AC | 356 ms | 56448 KB |
01-81.txt | AC | 365 ms | 58496 KB |
01-82.txt | AC | 378 ms | 61056 KB |
01-83.txt | AC | 408 ms | 60928 KB |
01-84.txt | AC | 390 ms | 61056 KB |
01-85.txt | AC | 358 ms | 56320 KB |
01-86.txt | AC | 359 ms | 56448 KB |
01-87.txt | AC | 354 ms | 56320 KB |
01-88.txt | AC | 416 ms | 61568 KB |
01-89.txt | AC | 380 ms | 61184 KB |
01-90.txt | AC | 388 ms | 61056 KB |
sample-01.txt | AC | 3 ms | 10496 KB |
sample-02.txt | AC | 3 ms | 10496 KB |
sample-03.txt | AC | 3 ms | 10496 KB |