Submission #993538

#	Time	Username	Problem	Language	Result	Execution time	Memory
993538		doducanh	Hard route (IZhO17_road)	C++14	0 / 100	3 ms	15756 KiB

road

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
const int maxn=5e5+7;
vector<int>adj[maxn];
int max_depth[maxn];
int max_count[maxn];
int max_hardness=0;
int paths_counts=1;
int n;
void dfs(int u,int par)
{
    for(int v:adj[u])if(v!=par){
        dfs(v,u);
        if(max_depth[u]<max_depth[v]+1){
            max_depth[u]=max_depth[v]+1;
            max_count[u]=max_count[v];
        }
        else if(max_depth[u]==max_depth[v]+1){
            max_count[u]+=max_count[v];
        }
    }
}
void dfs2(int u,int par,int parent_dist,int parent_count)
{
//    cout<<u<<" "<<max_hardness<<" "<<paths_counts<<" ";
    vector<pair<int,int>>tmp;
    if(u>1||adj[u].size()==1){
        tmp.push_back(make_pair(parent_dist,parent_count));
    }
    for(int v:adj[u])if(v!=par){
        tmp.push_back({max_depth[v]+1,max_count[v]});
    }
    sort(tmp.begin(),tmp.end(),greater<ii>());

    if(adj[u].size()>=3){
        int pre=0;
        int curr=0,tinh=0;
        int a=tmp[0].fi;
        int b=tmp[1].fi;
        int c=tmp[2].fi;
        for(ii p:tmp)
        {
            int len=p.fi;
            int num=p.se;
            if(len==c)pre+=num;
        }
        curr=1ll*a*(b+c);
        if(a!=b&&b!=c)
        {
            tinh=tmp[1].se*pre;
        } else if(a==b&&b==c)
        {
            tinh=pre*pre;
            for(ii p:tmp) {
                int len=p.fi;
                int num=p.se;
                if(len==a)tinh-=num*num;
            }
            tinh=tinh/2;
        } else if(a==b)
        {
            tinh=(tmp[0].se+tmp[1].se)*pre;
        } else
        {
            tinh=pre*pre;
            for(ii p:tmp) {
                int len=p.fi;
                int num=p.se;
                if(len==b)tinh-=num*num;

            }
            tinh=tinh/2;
        }
        if(curr>max_hardness)
        {
            max_hardness=curr;
            paths_counts=tinh;
        } else if(curr==max_hardness)paths_counts+=tinh;
    }

    int longest1=0;
    int count1=0;
    int longest2=0;
    int count2=0;
    for(ii p:tmp){
        int v=p.fi;
        int w=p.se;
        if(longest1<v+1){
            longest2=longest1;
            count2=count1;
            longest1=v+1;
            count1=w;
        }
        else if(longest1==v+1){
            count1+=w;
        }
        else if(longest2<v+1){
            longest2=v+1;
            count2=w;
        }
        else{
            count2+=w;
        }
    }
//    cout<<max_hardness<<" "<<paths_counts<<"\n";
    for(int v:adj[u])if(v!=par){
        if(max_depth[v]+2==longest1){
            if(max_count[v]==count1){
                dfs2(v,u,longest2,count2);
            }
            else{
                dfs2(v,u,longest1,count1-max_count[v]);
            }
        }
        else dfs2(v,u,longest1,count1);
    }

}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        max_depth[i]=0;
        max_count[i]=1;
    }
    dfs(1,0);
//    for(int i=1;i<=n;i++){
//        cout<<max_depth[i]<<" "<<max_count[i]<<"\n";
//    }
    dfs2(1,0,0,1);
    cout<<max_hardness<<" "<<paths_counts;
    return 0;
}

Compilation message (stderr)

road.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main()
      | ^~~~

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