Submission #476699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
476699	2021-09-28T09:04:23 Z	ogibogi2004	Shymbulak (IZhO14_shymbulak)	C++14	Compilation error	0 ms	0 KB

shymbulak

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
ll par[MAXN],n,depth[MAXN];
vector<ll>g[MAXN];
vector<ll>cycle;
bool vis[MAXN];
bool found;
ll x1,x2;
ll cycle_size;
void find_cycle(ll u,ll p)
{
    par[u]=p;
    for(auto xd:g[u])
    {
        if(par[xd]==0)
        {
            depth[xd]=depth[u]+1;
            find_cycle(xd,u);
        }
        else if(xd!=par[u]&&!found)
        {
            x1=u;
            x2=xd;
            found=1;
        }
    }
}
void make_cycle()
{
    if(depth[x1]<depth[x2])swap(x1,x2);
    cycle.push_back(x1);
    for(;;)
    {
        x1=par[x1];
        cycle.push_back(x1);
        if(x1==x2)break;
    }
}
pair<ll,ll> maxd[MAXN];
pair<ll,ll> calc(ll u)
{
    vis[u]=1;
    pair<ll,ll> ret={0,1};
    for(auto xd:g[u])
    {
        if(vis[xd])continue;
        pair<ll,ll> f=calc(xd);
        f.first++;
        if(f.first==ret.first)ret.second+=f.second;
        else if(f.first>ret.first)ret=f;
    }
    return maxd[u]=ret;
}
pair<ll,ll>maxdist;
ll ans;
ll val1[2*MAXN],val2[2*MAXN];
map<ll,ll> mp1;
int main()
{
    maxdist={0,0};
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        ll x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    find_cycle(1,-1);
    make_cycle();
    cycle_size=cycle.size();
    for(ll i=0;i<cycle_size;i++)
    {
        //cout<<cycle[i]<<" ";
        cycle.push_back(cycle[i]);
    }
    //cout<<endl;
    ll t=cycle_size/2;
    for(ll i=1;i<=cycle_size;i++)
    {
        vis[cycle[i]]=1;
    }
    for(ll i=1;i<=cycle_size;i++)
    {
        calc(cycle[i]);
    }
    multiset<ll>s1;
    for(ll i=0;i<cycle_size*2;i++)
    {
        val1[i]=-i+maxd[cycle[i]].first;
        val2[i]=i+maxd[cycle[i]].first;
    }
    for(ll i=0;i<t;i++)
    {
        s1.insert(val1[i]);
        mp1[val1[i]]+=maxd[cycle[i]].second;
        //s2.insert(val2[t+1+i]);
        //mp2[val2[t+1+i]]+=maxd[cycle[t+1+i]].second;
    }
    /*for(int i=0;i<cycle.size();i++)
    {
        cout<<cycle[i]<<" ";
    }
    cout<<endl;*/
    //cout<<t<<" "<<cycle[t]<<":\n";
    ll max1=(*s1.rbegin());
    //ll max2=(*s2.rbegin());
    ll cnt,dist;
    cnt=mp1[max1]*maxd[cycle[t]].second;
    dist=max1+t+maxd[cycle[t]].first;
    //cout<<dist<<" "<<cnt<<endl;
    if(dist>maxdist.first)
    {
        maxdist.first=dist;
        maxdist.second=0;
    }
    if(dist==maxdist.first)
    {
        maxdist.second+=cnt;
    }
    /*cnt=mp2[max2]*maxd[cycle[t]].second;
    dist=max2-t+maxd[cycle[t]].first;
    cout<<dist<<" "<<cnt<<endl;
    if(dist>maxdist.first)
    {
        maxdist.first=dist;
        maxdist.second=0;
    }
    if(dist==maxdist.first)
    {
        maxdist.second+=cnt;
    }*/
    for(ll mid=t+1;mid<cycle_size+t;mid++)
    {
        //cout<<mid<<" "<<cycle[mid]<<":\n";
        s1.erase(s1.find(val1[mid-t-1]));
        mp1[val1[mid-t-1]]-=maxd[cycle[mid-t-1]].second;
        //s2.erase(val2[mid]);
        //mp2[val2[mid]]-=maxd[cycle[mid]].second;
        s1.insert(val1[mid-1]);
        mp1[val1[mid-1]]+=maxd[cycle[mid-1]].second;
        //s2.insert(val2[mid+t]);
        //mp2[val2[mid+t]]+=maxd[cycle[mid+t]].second;
        max1=(*s1.rbegin());
        //max2=(*s2.rbegin());
        cnt=mp1[max1]*maxd[cycle[mid]].second;
        dist=max1+mid+maxd[cycle[mid]].first;
        //cout<<dist<<" "<<cnt<<endl;
        if(dist>maxdist.first)
        {
            maxdist.first=dist;
            maxdist.second=0;
        }
        if(dist==maxdist.first)
        {
            maxdist.second+=cnt;
        }
        /*cnt=mp2[max2]*maxd[cycle[mid]].second;
        dist=max2-mid+maxd[cycle[mid]].first;
        cout<<dist<<" "<<cnt<<endl;
        if(dist>maxdist.first)
        {
            maxdist.first=dist;
            maxdist.second=0;
        }
        if(dist==maxdist.first)
        {
            maxdist.second+=cnt;
        }
        */
        /*cout<<"s1:\n";
        for(auto xd:s1)cout<<xd<<" ";
        cout<<endl;*/
    }
    //cout<<maxdist.first<<" "<<maxdist.second<<endl;
    ans=maxdist.second;
    /*if(cycle_size%2==0)
    {
        for(ll i=0;i<t;i++)
        {
            ll j=i+t;
            ll dist=maxd[cycle[i]].first+t+maxd[cycle[j]].first;
            if(dist==maxdist.first)
            {
                ans+=maxd[cycle[i]].second*maxd[cycle[j]].second;
            }
        }
    }*/
    pair<ll,ll>ans1;
    ans1={0,0};
    for(int i=0;i<cycle_size;i++)
    {
        for(int j=i+1;j<cycle_size;j++)
        {
            int sd=min(j-i,cycle_size-j+i);
            ll cnt=maxd[cycle[i]].second*maxd[cycle[j]].second;
            if(j-i==cycle_size-j+i);
            cnt*=2;
            if(sd>ans1.first)
            {
                ans1.first=sd;ans1.second=0;
            }
            if(sd==ans1.first)
            {
                ans1.second+=cnt;
            }
        }
    }
    cout<<ans1.second<<endl;
    //cout<<ans<<endl;
return 0;
}
/*
8
1 2
2 3
2 4
2 5
2 8
3 6
6 4
4 7
*/

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:197:42: error: no matching function for call to 'min(int, long long int)'
  197 |             int sd=min(j-i,cycle_size-j+i);
      |                                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from shymbulak.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
shymbulak.cpp:197:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  197 |             int sd=min(j-i,cycle_size-j+i);
      |                                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from shymbulak.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
shymbulak.cpp:197:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  197 |             int sd=min(j-i,cycle_size-j+i);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from shymbulak.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
shymbulak.cpp:197:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  197 |             int sd=min(j-i,cycle_size-j+i);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from shymbulak.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
shymbulak.cpp:197:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  197 |             int sd=min(j-i,cycle_size-j+i);
      |                                          ^