Submission #1183986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183986		al_reem_2010	Hard route (IZhO17_road)	C++20	19 / 100	2093 ms	1472 KiB

road

// اَللَهُمَ صَلِ عَلَىَ مُحَمَدٍ وَ آلِ مُحَمَدٍ
#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <thread>
#include <fstream>
using namespace std ;
#define int long long
#define pb push_back
#define si size()
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define applejuice ios::sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
const int inf=1e18 ;
const int mod=1e9+7 ;
int tt=1 ;
int r=0 ;
int dis[5007] , fdis[5007] ;
vector<int> l[5007] ;
vector<int> a ;
vector<int> ans ;
vector<vector<int>> mm ;
bool dfs(int i , int j , int p)
{
    for(int k=0 ; k<l[i].si ; k++)
    {
        if(l[i][k]==p) {continue ;}
        if(l[i][k]==j) {mm[r].pb(l[i][k]) ; mm[r].pb(i) ; return 1 ;}
        if(dfs(l[i][k],j,i)) {mm[r].pb(i) ; return 1 ;}
    }
    return 0 ;
}
void dfs1(int k , int p , int m)
{
    dis[k]=m ;
    for(int i=0 ; i<l[k].si ; i++)
    {
        if(l[k][i]==p || l[k][i]==mm[r][0] || l[k][i]==mm[r][mm[r].si-1]) {continue ;}
        dfs1(l[k][i],k,dis[k]+1) ;
    }
}
void solve()
{
    int n ;
    cin >> n ;
    for(int i=0 ; i<n-1 ; i++) {int u , v ; cin >> u >> v ; l[u].pb(v) ; l[v].pb(u) ;}
    for(int i=1 ; i<=n ; i++) {if(l[i].si==1) {a.pb(i) ;}}
    for(int i=0 ; i<a.si ; i++)
    {
        for(int j=i+1 ; j<a.si ; j++)
        {
            mm.pb({}) ;
            r=mm.si-1 ;
            dfs(a[i],a[j],-1) ;
            if(mm[r].si==0) {continue ;}
            for(int k=1 ; k<=100 ; k++) {fdis[k]=inf ; dis[k]=-inf ;}
            for(int k=1 ; k<mm[r].si-1 ; k++)
            {
                dfs1(mm[r][k],-1,0) ;
                for(int h=1 ; h<=n ; h++) {fdis[h]=min(dis[h],fdis[h]) ;}
            }
            int anss=-inf ;
            for(int k=1 ; k<=n ; k++) {anss=max(fdis[k],anss) ;}
            if(a.si==2) {anss=0 ;}
            ans.pb((mm[r].si-1)*anss) ;
            r+=1 ;
        }
    }
    //for(int i=0 ; i<ans.si ; i++) {cout << ans[i] << " " ;} cout << "\n" ;
    int mx=*max_element(all(ans)) , cnt=0 ;
    for(int i=0 ; i<ans.si ; i++) {cnt+=(ans[i]==mx ? 1 : 0) ;}
    cout << mx << " " << cnt ;
}
signed main()
{
    //wrong
    applejuice ;
    //cin >> tt ;
    while(tt--) {solve() ;}
}
/*
 7
 1 2
 1 3
 2 4
 2 5
 3 6
 3 7
 
 4
 1 2
 2 3
 2 4
 
 5
 1 2
 2 3
 3 4
 4 5
 
 */

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