Submission #1184100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184100		ziyad_alharbi	Hard route (IZhO17_road)	C++20	19 / 100	2105 ms	196880 KiB

road

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ds[5005][5005],vs[5005],g1,g2;
set<int>st,rm;
vector<int>v[5005];
array<int,2>ans;
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int x=0;x<n-1;x++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int x=1;x<=n;x++)if(v[x].size()==1)st.insert(x);
    memset(ds,-1,sizeof ds);
    for(int x=1;x<=n;x++)
    {
        queue<array<int,2>>q;
        q.push({x,0});
        while(q.size())
        {
            auto [i,sz]=q.front();
            q.pop();
            ds[x][i]=sz;
            for(auto j:v[i])if(ds[x][j]==-1)q.push({j,sz+1});
        }
    }
    for(auto i:st)
    {
        for(auto j:st)
        {
            if(i>=j)continue;
            g1=i;
            g2=j;
            rm.clear();
            for(int x=1;x<=n;x++)vs[x]=0;
            queue<int>q;
            q.push(i);
            vs[i]=-1;
            while(q.size())
            {
                int x=q.front();
                q.pop();
                if(x==j)break;
                for(auto vr:v[x])
                {
                    if(vs[vr])continue;
                    vs[vr]=x;
                    q.push(vr);
                }
            }
            int jh=j;
            while(jh!=-1)
            {
                rm.insert(jh);
                jh=vs[jh];
            }
            int mx=0,vl=0;
            for(int x=1;x<=n;x++)
            {
                int mn=1e9;
                vl+=rm.count(x);
                for(auto ii:rm)
                {
                    mn=min(mn,ds[x][ii]);
                }
                mx=max(mx,mn);
            }
            int sz=rm.size()-1;
            if(mx*sz>ans[0])ans={mx*sz,1};
            else if(mx*sz==ans[0])ans[1]++;
        }
    }
    cout<<ans[0]<<' '<<ans[1]<<'\n';
    return 0;
}

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