제출 #298895

#제출 시각아이디문제언어결과실행 시간메모리
298895BruteforcemanTax Evasion (LMIO19_mokesciai)C++11
39 / 100
151 ms13048 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...