제출 #1118424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118424		Younis_Dwai	Hard route (IZhO17_road)	C++14	19 / 100	2054 ms	848 KiB

road

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define int long long
#define in insert
#define mid (l+r)/2
#define in insert
using namespace std;
const int N=5e3+5;
int n,depth[N],p[N],dis[N],mx=0,ret=0;
vector<int> adj[N];
void dfs(int node , int par){
     p[node]=par;
     for(auto u : adj[node]){
         if(u==par) continue ;
         depth[u]=1+depth[node];
         dfs(u,node);
     }
     return ;
}
void calc(int u , int v){
     for(int i=1;i<=n;i++) dis[i]=1e5;
     queue<int> q;
     dis[v]=dis[u]=0;
     q.push(v);
     int ct=0;
     while(v!=u){
           v=p[v];
           dis[v]=0;
           q.push(v);
           ++ct;
     }
     while(!q.empty()){
           int node=q.front();
           q.pop();
           for(auto u : adj[node]){
               if(dis[u]>1+dis[node]){
                  dis[u]=1+dis[node];
                  q.push(u);
               }
           }
     }
     int bb=0;
     for(int i=1;i<=n;i++){
         bb=max(bb,dis[i]);
     }
     if(ct*bb==mx) ret++;
     else if(ct*bb>mx){
           ret=1;
           mx=ct*bb;
     }
     return ;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(adj[i].size()!=1 || adj[j].size()!=1) continue ;
            depth[i]=0;
            dfs(i,i);
            calc(i,j);
        }
    }
    cout<<mx<<' '<<ret;
    return 0;
}

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