이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
vector <int> g[maxn];
int par[maxn];
int dep[maxn];
int vis[maxn];
void dfs(int x) {
for(int i : g[x]) {
dep[i] = 1 + dep[x];
dfs(i);
}
}
pair <int, int> getFarthest(int x) {
if(vis[x]) return make_pair(0, x);
pair <int, int> ans (dep[x], x);
for(int i : g[x]) {
ans = max(ans, getFarthest(i));
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 2; i <= n; i++) {
cin >> par[i];
g[par[i]].push_back(i);
}
dep[1] = 1;
dfs(1);
vector <pair <int, int>> v;
for(int i = 1; i <= m; i++) {
int x;
cin >> x;
v.emplace_back(dep[x], x);
if(x == 1) {
cout << 1 << endl;
exit(0);
}
}
for(auto &i : v) {
int top = (i.first + 1) / 2;
while(top + 1 < dep[i.second]) {
i.second = par[i.second];
}
i.first = dep[i.second];
}
sort(v.begin(), v.end(), greater <pair <int, int>> ());
int ans = n;
for(auto &i : v) {
auto j = getFarthest(i.second);
vis[j.second] = true;
ans = min(ans, j.first);
}
cout << ans << endl;
return 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... |