Submission #739946

#	Time	Username	Problem	Language	Result	Execution time	Memory
739946		victor_gao	Hard route (IZhO17_road)	C++17	0 / 100	7 ms	12080 KiB

road

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 500015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,mx[N],dp[N],dp1[N],fa[N],ans=0,cnt=0;
vector<int>g[N];
void dfs(int p,int lp){
    fa[p]=lp;
    for (auto i:g[p]){
        if (i!=lp){
            dfs(i,p);
            mx[p]=max(mx[p],mx[i]+1);
        }
    }
    dp[p]=mx[p];
}
void dfs1(int p,int lp,int val){
    int mx1=val,mx2=-1;
    for (auto i:g[p]){
        if (i!=lp){
            mx2=max(mx2,dp[i]);
            if (mx2>mx1) swap(mx1,mx2);
        }
    }
    mx1++; mx2++;
    for (auto i:g[p]){
        if (i!=lp){
            if (dp[i]==mx1-1){
                dp1[i]=mx2+1;
                dfs1(i,p,mx2);
            }
            else {
                dp1[i]=mx1+1;
                dfs1(i,p,mx1);
            }
        }
    }
}
void relax(int val){
    if (val>ans)
        ans=val,cnt=1;
    else if (val==ans)
        cnt++;
}
void solve(){
    for (int j=1;j<=n;j++){
        vector<int>dep;
        for (auto i:g[j]){
            if (i!=fa[j])
                dep.push_back(dp[i]+1);
        }
        dep.push_back(dp1[j]);
        sort(dep.begin(),dep.end());
        if (dep.size()<=2) relax(0);
        else {
            int b1=dep.back(),b2=dep[dep.size()-2],b3=dep[dep.size()-3];
            for (int i=0;i<dep.size()-2;i++)
                relax(dep[i]*(b2+b1));
            relax(b2*(b1+b3));
            relax(b1*(b2+b3));
        }
    }
}
signed main(){
    fast
    cin>>n;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    dfs1(1,0,-1);
    solve();
    if (ans) cout<<ans<<" "<<cnt<<'\n';
    else cout<<ans<<' '<<1<<'\n';
}

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:69:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int i=0;i<dep.size()-2;i++)
      |                          ~^~~~~~~~~~~~~

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