結果
問題 | No.2634 Tree Distance 3 |
ユーザー | PersistentLife |
提出日時 | 2024-02-16 21:52:42 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 315 ms / 3,000 ms |
コード長 | 2,607 bytes |
コンパイル時間 | 1,836 ms |
コンパイル使用メモリ | 179,436 KB |
実行使用メモリ | 98,896 KB |
最終ジャッジ日時 | 2024-02-16 21:53:12 |
合計ジャッジ時間 | 20,822 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 307 ms
94,592 KB |
testcase_01 | AC | 315 ms
94,592 KB |
testcase_02 | AC | 309 ms
94,592 KB |
testcase_03 | AC | 303 ms
94,592 KB |
testcase_04 | AC | 292 ms
94,592 KB |
testcase_05 | AC | 291 ms
94,592 KB |
testcase_06 | AC | 305 ms
94,592 KB |
testcase_07 | AC | 277 ms
94,592 KB |
testcase_08 | AC | 233 ms
91,884 KB |
testcase_09 | AC | 211 ms
91,984 KB |
testcase_10 | AC | 236 ms
92,028 KB |
testcase_11 | AC | 219 ms
91,996 KB |
testcase_12 | AC | 221 ms
91,920 KB |
testcase_13 | AC | 220 ms
92,040 KB |
testcase_14 | AC | 222 ms
91,884 KB |
testcase_15 | AC | 230 ms
91,920 KB |
testcase_16 | AC | 187 ms
94,016 KB |
testcase_17 | AC | 109 ms
86,244 KB |
testcase_18 | AC | 140 ms
87,704 KB |
testcase_19 | AC | 163 ms
92,588 KB |
testcase_20 | AC | 56 ms
72,784 KB |
testcase_21 | AC | 287 ms
96,584 KB |
testcase_22 | AC | 240 ms
98,204 KB |
testcase_23 | AC | 254 ms
98,896 KB |
testcase_24 | AC | 250 ms
94,424 KB |
testcase_25 | AC | 243 ms
93,568 KB |
testcase_26 | AC | 257 ms
94,708 KB |
testcase_27 | AC | 232 ms
93,548 KB |
testcase_28 | AC | 265 ms
94,308 KB |
testcase_29 | AC | 242 ms
93,856 KB |
testcase_30 | AC | 253 ms
93,480 KB |
testcase_31 | AC | 248 ms
93,484 KB |
testcase_32 | AC | 261 ms
93,504 KB |
testcase_33 | AC | 165 ms
88,368 KB |
testcase_34 | AC | 38 ms
59,708 KB |
testcase_35 | AC | 94 ms
83,360 KB |
testcase_36 | AC | 58 ms
71,168 KB |
testcase_37 | AC | 112 ms
84,116 KB |
testcase_38 | AC | 12 ms
43,292 KB |
testcase_39 | AC | 12 ms
43,304 KB |
testcase_40 | AC | 12 ms
43,256 KB |
testcase_41 | AC | 11 ms
43,248 KB |
testcase_42 | AC | 12 ms
43,248 KB |
testcase_43 | AC | 79 ms
80,160 KB |
testcase_44 | AC | 55 ms
68,776 KB |
testcase_45 | AC | 222 ms
89,776 KB |
testcase_46 | AC | 138 ms
84,796 KB |
testcase_47 | AC | 265 ms
90,856 KB |
testcase_48 | AC | 284 ms
93,496 KB |
testcase_49 | AC | 256 ms
93,492 KB |
testcase_50 | AC | 270 ms
93,484 KB |
testcase_51 | AC | 251 ms
93,480 KB |
testcase_52 | AC | 265 ms
93,508 KB |
testcase_53 | AC | 11 ms
43,252 KB |
testcase_54 | AC | 12 ms
43,252 KB |
testcase_55 | AC | 12 ms
43,248 KB |
testcase_56 | AC | 12 ms
43,248 KB |
testcase_57 | AC | 11 ms
43,252 KB |
testcase_58 | AC | 8 ms
26,788 KB |
testcase_59 | AC | 7 ms
26,788 KB |
testcase_60 | AC | 290 ms
92,776 KB |
testcase_61 | AC | 285 ms
92,784 KB |
testcase_62 | AC | 302 ms
92,780 KB |
testcase_63 | AC | 202 ms
89,528 KB |
testcase_64 | AC | 142 ms
84,504 KB |
testcase_65 | AC | 189 ms
89,008 KB |
testcase_66 | AC | 65 ms
72,904 KB |
testcase_67 | AC | 54 ms
70,404 KB |
testcase_68 | AC | 210 ms
91,872 KB |
testcase_69 | AC | 206 ms
91,872 KB |
testcase_70 | AC | 209 ms
91,872 KB |
ソースコード
/* Things to notice: 1. do not calculate useless values 2. do not use similar names Things to check: 1. submit the correct file 2. time (it is log^2 or log) 3. memory 4. prove your naive thoughts 5. long long 6. corner case like n=0,1,inf or n=m 7. check if there is a mistake in the ds or other tools you use 8. fileio in some oi-contest 9. module on time 10. the number of a same divisor in a math problem 11. multi-information and queries for dp and ds problems */ #include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<long long,long long> #define mp make_pair #define pb push_back const int mod=998244353; const int inf=0x3f3f3f3f; const int INF=1e18; vector <pii > g[200005]; struct LCA { int dep[200005],dfn[200005],times; int dist[200005]; int st[20][400005],Lg[400005]; void dfs(int u,int fa) { dfn[u]=++times,st[0][times]=u; for(int i=0;i<g[u].size();i++) { int v=g[u][i].fi; if(v==fa) continue; dep[v]=dep[u]+1,dist[v]=dist[u]+1LL*g[u][i].se,dfs(v,u); st[0][++times]=u; } } int mindep(int x,int y) { if(dep[x]<dep[y]) return x; return y; } void build() { times=0,dep[1]=dist[1]=0; dfs(1,-1); Lg[1]=0,Lg[2]=1; for(int i=3;i<=times;i++) Lg[i]=Lg[i/2]+1; for(int k=1;k<20;k++) for(int i=1;i+(1<<k)-1<=times;i++) st[k][i]=mindep(st[k-1][i],st[k-1][i+(1<<(k-1))]); } int getlca(int u,int v) { u=dfn[u],v=dfn[v]; if(u>v) swap(u,v); int s=Lg[v-u+1]; return mindep(st[s][u],st[s][v-(1<<s)+1]); } int getdis(int u,int v) { int l=getlca(u,v); return dist[u]+dist[v]-2LL*dist[l]; } }Lca; int n; int a[200005],ans[200005]; pii b[200005]; void solve() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i],b[i]=mp(a[i],i); sort(b+1,b+1+n),reverse(b+1,b+1+n); for(int i=1;i<n;i++) { int u,v; cin>>u>>v; g[u].pb(mp(v,1)),g[v].pb(mp(u,1)); } Lca.build(); pii diam=mp(-1,-1); for(int i=1;i<=n;i++) { int j=i; while(j+1<=n&&b[j+1].fi==b[j].fi) j++; for(int l=i;l<=j;l++) { int u=b[l].se; if(diam==mp(-1LL,-1LL)) diam=mp(u,u); else { int x=diam.fi,y=diam.se; if(Lca.getdis(u,x)>=Lca.getdis(x,y)&&Lca.getdis(u,x)>=Lca.getdis(u,y)) diam=mp(u,x); else if(Lca.getdis(u,y)>=Lca.getdis(x,y)&&Lca.getdis(u,y)>=Lca.getdis(u,x)) diam=mp(u,y); else diam=mp(x,y); } } for(int l=i;l<=j;l++) { int u=b[l].se; ans[u]=max(Lca.getdis(u,diam.fi),Lca.getdis(u,diam.se)); } i=j; } for(int i=1;i<=n;i++) cout<<ans[i]<<" "; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int _=1; // cin>>_; while(_--) solve(); return 0; }