Submission #1168358

#TimeUsernameProblemLanguageResultExecution timeMemory
1168358SyedSohaib_123Triumphal arch (POI13_luk)C++20
0 / 100
460 ms87400 KiB
#include <bits/stdc++.h> using namespace std; #define append push_back #define int long long const int N=3e6+10,LG=21; int mod=1e9+7; vector<int>g[N]; int s=0,deg[N],ans=0,p[N]; void dfs(int node,int ind,int par=-1){ p[node]=par; ans=max(ans,(s+ind-1)/ind); for(auto i:g[node]){ if(i==p[node]) continue; s+=deg[i]-1; dfs(i,ind+1,node); s-=deg[i]-1; } } void dfs2(int node,int ind,int par=-1){ ans=max(ans,(s+ind-1)/ind); for(auto i:g[node]){ if(i==p[node]) continue; s+=deg[i]-1; dfs2(i,ind+1,node); s-=deg[i]-1; } } void solve(int tst){ int n; cin>>n; for(int i=1;i<n;i++){ int a,b; cin>>a>>b; deg[a]++; deg[b]++; g[a].append(b); g[b].append(a); } s=ans=deg[1]; dfs(1,1); for(int i=2;i<=n;i++) s=deg[i]-1,dfs2(i,1); cout<<ans<<endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; // cin >> t; for(int i=1;i<=t;i++){ solve(i); // if(i!=t) cout<<endl; } }
#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...