9668 2024. 02. 23 21:21:42 999 Átvágás (75 pont) cpp17 Hibás válasz 8/75 236ms 29864 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 Összpont Teszt Verdikt Idő Memória
base 8/75
1 Elfogadva 0/0 3ms 1812 KiB
2 Elfogadva 0/0 3ms 2000 KiB
3 Hibás válasz 0/0 10ms 3212 KiB
4 Részben helyes 2/4 3ms 2296 KiB
5 Hibás válasz 0/4 3ms 2428 KiB
6 Részben helyes 2/4 3ms 2544 KiB
7 Hibás válasz 0/4 3ms 2680 KiB
8 Hibás válasz 0/4 3ms 2760 KiB
9 Hibás válasz 0/4 3ms 2896 KiB
10 Részben helyes 2/4 148ms 29484 KiB
11 Hibás válasz 0/4 163ms 29188 KiB
12 Hibás válasz 0/4 181ms 29860 KiB
13 Hibás válasz 0/4 185ms 29864 KiB
14 Hibás válasz 0/4 199ms 28952 KiB
15 Hibás válasz 0/4 209ms 27552 KiB
16 Hibás válasz 0/4 212ms 27028 KiB
17 Hibás válasz 0/4 217ms 27308 KiB
18 Hibás válasz 0/5 212ms 27076 KiB
19 Hibás válasz 0/6 216ms 27120 KiB
20 Hibás válasz 0/6 236ms 26992 KiB
21 Elfogadva 2/2 3ms 3808 KiB