Submission #333990

#	Time	Username	Problem	Language	Result	Execution time	Memory
333990		juggernaut	Hard route (IZhO17_road)	C++14	52 / 100	567 ms	1132 KiB

road

#include<bits/stdc++.h>
using namespace std;
int n,dp[5005],ans,cnt,id[5005],root,dp2[5005];
bool leaf[5005];
vector<int>g[5005];
void build(int v,int p){
    dp[v]=0;
    dp2[v]=0;
    for(int to:g[v])if(to!=p){
        build(to,v);
        if(dp[to]+1>dp[v]){
            dp[v]=dp[to]+1;
            id[v]=to;
        }
    }
    for(int to:g[v])if(to!=p&&to!=id[v])dp2[v]=max(dp2[v],dp[to]+1);
}
void dfs(int v,int p,int depth,int mx){
    if(v!=root&&leaf[v]&&leaf[root]){
        //cout<<root<<"-"<<v<<" "<<depth<<" "<<max(mx,dp[v])<<endl;
        int tmp=depth*max(mx,dp[v]);
        if(tmp>ans){
            ans=tmp;
            cnt=1;
        }else if(tmp==ans)cnt++;
    }
    for(int to:g[v])if(to!=p){
        if(to==id[v]){
            dfs(to,v,depth+1,max(mx,dp2[v]));
        }else{
            dfs(to,v,depth+1,max(mx,dp[v]));
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++)leaf[i]=(g[i].size()==1);
    for(root=1;root<=n;root++){
        if(!leaf[root])continue;
        build(root,root);
        dfs(root,root,0,0);
    }
    if(ans==0)cnt=2;
    printf("%d %d",ans,(cnt>>1));
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
road.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 0 / 48