제출 #1168188

#제출 시각아이디문제언어결과실행 시간메모리
1168188UmairAhmadMirza새로운 문제 (POI13_luk)C++20
100 / 100
386 ms25100 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int const N=3e5+5; int const mod=1e9+7; vector<int> adj[N]; int dp[N],n,cur; void dfs(int node,int par){ dp[node]=adj[node].size(); if(par>0) dp[node]--; dp[node]-=cur; for(int i:adj[node]) if(i!=par){ dfs(i,node); dp[node]+=dp[i]; } dp[node]=max(dp[node],0); } bool solve(int k){ for (int i = 0; i <=n; ++i) dp[i]=0; cur=k; dfs(1,0); return (dp[1]==0); } int main(){ cin>>n; for (int i = 1; i < n; ++i) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } int low=-1,high=n; while(high-low>1){ int mid=(high+low)/2; if(solve(mid)) high=mid; else low=mid; } cout<<high<<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...
#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...