96682024-02-23 21:21:42999Átvágás (75 pont)cpp17Hibás válasz 8/75236ms29864 KiB
#include <bits/stdc++.h>
using namespace std;

int main() 
{
  int n;cin>>n;
  vector<vector<int>> v(n+1);
  for(int i = 0;i<n-1;i++){
    int a,b;cin>>a>>b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  vector<int> dis(n+1,-1);
  dis[1]=0;
  queue<int> q;
  q.push(1);
  while(!q.empty()){
    int node=q.front();
    q.pop();
    for(int i : v[node]){
      if(dis[i]==-1){
        q.push(i);
        dis[i]=dis[node]+1;
      }
    }
  }
  int maxdis=1;
  for(int i = 1;i<=n;i++){
    if(dis[maxdis]<dis[i])maxdis=i;
  }
  fill(dis.begin(),dis.end(),-1);
  dis[maxdis]=1;
  q.push(maxdis);
  while(!q.empty()){
    int node=q.front();
    q.pop();
    for(int i : v[node]){
      if(dis[i]!=-1)continue;
      q.push(i);
      dis[i]=dis[node]+1;
    }
  }
  for(int i = 1;i<=n;i++){
    if(dis[maxdis]<dis[i])maxdis=i;
  }
  cout<<n-dis[maxdis]<<' ';
  //task 2:
  int cnt=0;
  int db=0;
  int sum=0;
  for(int i = 1;i<=n;i++){
    if(cnt==v[i].size())db++;
    else if(cnt<v[i].size()){
      sum+=v[cnt].size()-1;
      db=1;
      cnt=v[i].size();
    }
    else if(v[i].size()!=1){
      sum+=v[i].size()-1;
    }
  }
  int ans2=(db-1)*cnt+sum;
  cout<<ans2<<endl;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base8/75
1Elfogadva0/03ms1812 KiB
2Elfogadva0/03ms2000 KiB
3Hibás válasz0/010ms3212 KiB
4Részben helyes2/43ms2296 KiB
5Hibás válasz0/43ms2428 KiB
6Részben helyes2/43ms2544 KiB
7Hibás válasz0/43ms2680 KiB
8Hibás válasz0/43ms2760 KiB
9Hibás válasz0/43ms2896 KiB
10Részben helyes2/4148ms29484 KiB
11Hibás válasz0/4163ms29188 KiB
12Hibás válasz0/4181ms29860 KiB
13Hibás válasz0/4185ms29864 KiB
14Hibás válasz0/4199ms28952 KiB
15Hibás válasz0/4209ms27552 KiB
16Hibás válasz0/4212ms27028 KiB
17Hibás válasz0/4217ms27308 KiB
18Hibás válasz0/5212ms27076 KiB
19Hibás válasz0/6216ms27120 KiB
20Hibás válasz0/6236ms26992 KiB
21Elfogadva2/23ms3808 KiB