Submission #1168365

#TimeUsernameProblemLanguageResultExecution timeMemory
1168365Jawad_Akbar_JJTriumphal arch (POI13_luk)C++20
20 / 100
527 ms17488 KiB
#include <iostream> #include <vector> using namespace std; vector<int> nei[300005]; int dfs(int u, int p, int md){ vector<int> vec; int l = -1, r = 0, cnt = 0; for (int i : nei[u]) if (i != p) vec.push_back(dfs(i, u, md)), r = max(r, vec.back()), cnt++; if (cnt >= md) return r + cnt - md; while (l + 1 < r){ int mid = (l + r) / 2, sm = cnt; for (int &i : vec) sm += max(0, i - mid); if (sm <= md) r = mid; else l = mid; } return r; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; for (int i=1;i<n;i++){ int a, b; cin>>a>>b; nei[a].push_back(b); nei[b].push_back(a); } int l = 0, r = n; while (l + 1 < r){ int mid = (l + r) / 2; if (dfs(1, 1, mid) == 0) r = mid; else l = mid; } cout<<r<<'\n'; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...