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 |