제출 #832922

#제출 시각아이디문제언어결과실행 시간메모리
832922winter0101Cat Exercise (JOI23_ho_t4)C++14
41 / 100
208 ms114740 KiB
#include <bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define int long long const int maxn=2e5+9; vector<int>a[maxn]; int b[maxn]; int rev[maxn]; long long ans=0; int dep[maxn]; int st[maxn][19],jump[maxn][19]; vector<pii>d[maxn]; void dfs(int u,int par){ for (auto v:a[u]){ if (v==par)continue; dep[v]=dep[u]+1; st[v][0]=b[u]; jump[v][0]=u; for1(i,1,18){ jump[v][i]=jump[jump[v][i-1]][i-1]; st[v][i]=max(st[v][i-1],st[jump[v][i-1]][i-1]); } if (dep[v]>0){ int mx=0; int nv=v; for2(j,18,0){ if (st[nv][j]==0)continue; if (st[nv][j]<b[v]){ mx=max(mx,st[nv][j]); nv=jump[nv][j]; } } if (mx>0)d[v].pb({rev[mx],dep[v]-dep[rev[mx]]}); nv=st[nv][0]; d[rev[nv]].pb({v,dep[v]-dep[rev[nv]]}); } dfs(v,u); } } long long f[maxn]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; for1(i,1,n){ cin>>b[i]; rev[b[i]]=i; } for1(i,1,n-1){ int u,v; cin>>u>>v; a[u].pb(v); a[v].pb(u); } int root; for1(i,1,n)if (b[i]==n)root=i; dfs(root,0); /*for1(i,1,n){ for (auto v:d[i]){ cout<<i<<" "<<v.fi<<" "<< v.se<<'\n'; } }*/ for1(i,1,n){ for (auto v:d[rev[i]]){ f[rev[i]]=max(f[rev[i]],f[v.fi]+v.se); } ans=max(ans,f[rev[i]]); } cout<<ans; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int32_t main()':
Main.cpp:71:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     dfs(root,0);
      |     ~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...