이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |