제출 #961001

#제출 시각아이디문제언어결과실행 시간메모리
961001tudor_costinCat Exercise (JOI23_ho_t4)C++11
31 / 100
1095 ms1048576 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int Nmax=2e5+5; int a[Nmax]; int nodes[Nmax],dp[Nmax],pos[Nmax],activ[Nmax],p[Nmax]; int nodedepth[Nmax]; pair<int,int> aint[4*Nmax]; vector<int> euler; vector<int> depths; vector<int> v[Nmax]; int n; int sol=0; int sef(int x) { if(p[x]==x) return x; p[x]=sef(p[x]); return p[x]; } bool cmp(int x,int y) { return a[x]<a[y]; } void build(int nod,int l,int r) { if(l==r) { aint[nod]={depths[l],euler[l]}; return; } int mid=(l+r)/2; build(2*nod,l,mid); build(2*nod+1,mid+1,r); aint[nod]=min(aint[2*nod],aint[2*nod+1]); return; } pair<int,int> query(int nod,int l,int r,int st,int dr) { if(st<=l && r<=dr) return aint[nod]; int mid=(l+r)/2; if(dr<=mid) return query(2*nod,l,mid,st,dr); if(mid<st) return query(2*nod+1,mid+1,r,st,dr); return min(query(2*nod,l,mid,st,mid),query(2*nod+1,mid+1,r,mid+1,dr)); } void dfs(int nod,int prev,int depth) { euler.push_back(nod); depths.push_back(depth); nodedepth[nod]=depth; pos[nod]=euler.size()-1; for(auto u:v[nod]) { if(u!=prev) { dfs(u,nod,depth+1); euler.push_back(nod); depths.push_back(depth); } } } int lca(int u,int v) { if(pos[u]>pos[v]) swap(u,v); return query(1,0,euler.size()-1,pos[u],pos[v]).second; } void calclca() { dfs(1,0,0); build(1,0,euler.size()-1); } int dist(int u,int v) { int nod=lca(u,v); return nodedepth[u]+nodedepth[v]-2*nodedepth[nod]; } void unite(int x,int y) { int sefx=sef(x); int sefy=sef(y); if(a[sefx]<a[sefy]) swap(sefx,sefy); p[sefy]=sefx; return; } void activate(int nod) { activ[nod]=1; p[nod]=nod; for(auto u:v[nod]) { if(activ[u]) { int nxt=sef(u); dp[nod]=max(dp[nod],dist(nod,nxt)+dp[nxt]); unite(nod,u); } } } signed main() { cin>>n; int start; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]==n) start=i; nodes[i]=i; } sort(nodes+1,nodes+n+1,cmp); bool ok=0; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } calclca(); for(int i=1;i<=n;i++) { activate(nodes[i]); } cout<<dp[nodes[n]]<<'\n'; return 0; }

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

Main.cpp: In function 'int main()':
Main.cpp:101:9: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  101 |     int start;
      |         ^~~~~
Main.cpp:109:10: warning: unused variable 'ok' [-Wunused-variable]
  109 |     bool ok=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...