Submission #2313164
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 | luogu_bot3 |
Language | C++ (GCC 5.4.1) |
Score | 1900 |
Code Size | 1828 Byte |
Status | AC |
Exec Time | 620 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 | 21 ms | 12032 KB |
01-05.txt | AC | 585 ms | 54144 KB |
01-06.txt | AC | 521 ms | 56192 KB |
01-07.txt | AC | 522 ms | 54144 KB |
01-08.txt | AC | 533 ms | 54144 KB |
01-09.txt | AC | 538 ms | 54144 KB |
01-10.txt | AC | 551 ms | 54144 KB |
01-11.txt | AC | 561 ms | 54144 KB |
01-12.txt | AC | 571 ms | 54144 KB |
01-13.txt | AC | 578 ms | 54144 KB |
01-14.txt | AC | 595 ms | 56192 KB |
01-15.txt | AC | 593 ms | 56192 KB |
01-16.txt | AC | 583 ms | 56192 KB |
01-17.txt | AC | 573 ms | 54144 KB |
01-18.txt | AC | 568 ms | 54144 KB |
01-19.txt | AC | 555 ms | 54144 KB |
01-20.txt | AC | 522 ms | 60800 KB |
01-21.txt | AC | 517 ms | 60800 KB |
01-22.txt | AC | 532 ms | 60800 KB |
01-23.txt | AC | 546 ms | 60800 KB |
01-24.txt | AC | 571 ms | 60800 KB |
01-25.txt | AC | 572 ms | 60800 KB |
01-26.txt | AC | 584 ms | 60800 KB |
01-27.txt | AC | 596 ms | 60800 KB |
01-28.txt | AC | 606 ms | 60800 KB |
01-29.txt | AC | 602 ms | 60800 KB |
01-30.txt | AC | 178 ms | 25472 KB |
01-31.txt | AC | 182 ms | 25472 KB |
01-32.txt | AC | 181 ms | 25472 KB |
01-33.txt | AC | 178 ms | 25472 KB |
01-34.txt | AC | 172 ms | 25472 KB |
01-35.txt | AC | 524 ms | 71296 KB |
01-36.txt | AC | 548 ms | 71296 KB |
01-37.txt | AC | 556 ms | 71296 KB |
01-38.txt | AC | 577 ms | 71296 KB |
01-39.txt | AC | 600 ms | 71296 KB |
01-40.txt | AC | 620 ms | 71296 KB |
01-41.txt | AC | 99 ms | 21376 KB |
01-42.txt | AC | 99 ms | 21376 KB |
01-43.txt | AC | 100 ms | 21376 KB |
01-44.txt | AC | 99 ms | 21376 KB |
01-45.txt | AC | 558 ms | 58368 KB |
01-46.txt | AC | 550 ms | 58368 KB |
01-47.txt | AC | 555 ms | 58368 KB |
01-48.txt | AC | 468 ms | 71296 KB |
01-49.txt | AC | 464 ms | 71296 KB |
01-50.txt | AC | 461 ms | 71296 KB |
01-51.txt | AC | 454 ms | 71296 KB |
01-52.txt | AC | 499 ms | 71296 KB |
01-53.txt | AC | 495 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 | 386 ms | 54144 KB |
01-58.txt | AC | 442 ms | 60416 KB |
01-59.txt | AC | 452 ms | 60416 KB |
01-60.txt | AC | 385 ms | 62464 KB |
01-61.txt | AC | 393 ms | 56320 KB |
01-62.txt | AC | 409 ms | 56192 KB |
01-63.txt | AC | 389 ms | 54144 KB |
01-64.txt | AC | 460 ms | 60928 KB |
01-65.txt | AC | 453 ms | 61056 KB |
01-66.txt | AC | 456 ms | 61184 KB |
01-67.txt | AC | 406 ms | 56320 KB |
01-68.txt | AC | 412 ms | 56320 KB |
01-69.txt | AC | 409 ms | 56320 KB |
01-70.txt | AC | 409 ms | 63232 KB |
01-71.txt | AC | 407 ms | 63232 KB |
01-72.txt | AC | 401 ms | 63488 KB |
01-73.txt | AC | 352 ms | 56320 KB |
01-74.txt | AC | 346 ms | 56320 KB |
01-75.txt | AC | 336 ms | 56320 KB |
01-76.txt | AC | 373 ms | 62464 KB |
01-77.txt | AC | 387 ms | 60416 KB |
01-78.txt | AC | 371 ms | 60416 KB |
01-79.txt | AC | 343 ms | 56320 KB |
01-80.txt | AC | 356 ms | 56448 KB |
01-81.txt | AC | 366 ms | 58496 KB |
01-82.txt | AC | 381 ms | 61056 KB |
01-83.txt | AC | 411 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 | 353 ms | 56320 KB |
01-88.txt | AC | 419 ms | 61568 KB |
01-89.txt | AC | 380 ms | 61184 KB |
01-90.txt | AC | 389 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 |