Submission #448162

#TimeUsernameProblemLanguageResultExecution timeMemory
448162jk410Papričice (COCI20_papricice)C++17
0 / 110
1 ms332 KiB
#include <bits/stdc++.h> using namespace std; const int INF=1e9; int N,Ans=INF; int Size[2001]; vector<int> Edge[2001]; vector<pair<int,int>> Edge_List; void dfs(int v,int par){ Size[v]=1; for (int i:Edge[v]){ if (i==par) continue; dfs(i,v); Size[v]+=Size[i]; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>N; for (int i=1; i<N; i++){ int a,b; cin>>a>>b; Edge[a].push_back(b); Edge[b].push_back(a); Edge_List.push_back({a,b}); } for (auto i:Edge_List){ for (int j=1; j<=N; j++) Size[j]=0; dfs(i.second,i.first); for (int j=1; j<=N; j++){ if (!Size[j]||j==i.second) continue; Ans=min(Ans,max({Size[j],Size[i.second]-Size[j],N-Size[i.second]})-min({Size[j],Size[i.second]-Size[j],N-Size[i.second]})); } } cout<<Ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...