Submission #1183602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183602		ziyad_alharbi	Hard route (IZhO17_road)	C++20	0 / 100	12 ms	12172 KiB

road

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,s;
set<int>st,rm;
vector<int>v[500000];
array<int,2>ans;
bool bln;
bool f(int i,int o,int j)
{
    rm.insert(i);
    if(i==j)return bln=1;
    for(auto x:v[i])
    {
        if(x==o)continue;
        f(x,i,j);
        if(bln)return bln=1;
    }
    if(bln)return bln=1;
    rm.erase(i);
    return bln=0;
}
void bfs()
{
    queue<array<int,3>>q;
    for(auto i:st)if(!rm.count(i))q.push({i,0,0});
    int mx=0;
    while(q.size())
    {
        auto [i,sz,o]=q.front();
        q.pop();
        mx=sz;
        if(rm.count(i))continue;
        for(auto j:v[i])
        {
            if(j==o)continue;
            q.push({j,sz+1,i});
        }
    }
    if(mx*s>ans[0])ans={mx*s,1};
    else if(mx*s==ans[0])ans[1]++;
}
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);
    }
    ans={0,0};
    for(int x=1;x<=n;x++)if(v[x].size()==1)st.insert(x);
    for(auto i:st)
    {
        for(auto ji=st.upper_bound(i);ji!=st.end();ji++)
        {
            rm.clear();
            bln=0;
            int j=*ji;
            f(i,0,j);
            s=rm.size()-1;
            bfs();
        }
    }
    cout<<ans[0]<<' '<<ans[1]<<'\n';
    return 0;
}

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