제출 #883653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883653		alexdd	관광지 (IZhO14_shymbulak)	C++17	50 / 100	1553 ms	21272 KiB

shymbulak

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
int n;
vector<int> con[200005];
bool visited[200005];
int parent[200005];
bool iscyc[200005];
int maxd[200005];
int cntmax[200005];
int depth[200005];
int tin[200005];
int tout[200005];
int timer;
bool gasit=0;
pair<int,int> capete;
int maxdist=0,cate=0;
vector<int> cyc;
bool isanc(int x, int y)
{
    if(tin[x]<=tin[y] && tout[x]>=tout[y])
        return 1;
    return 0;
}
void dfs_find(int nod)
{
    //if(gasit) return;
    tin[nod]=++timer;
    visited[nod]=1;
    for(auto adj:con[nod])
    {
        if(!visited[adj])
        {
            parent[adj]=nod;
            dfs_find(adj);
        }
        else if(adj!=parent[nod]) ///am gasit cyclu
        {
            if(gasit && (capete.first != adj || capete.second != nod))
            {
                while(1)
                    n=0;
            }
            gasit=1;
            capete = {nod,adj};
        }
    }
    tout[nod]=++timer;
}
void find_cycle()
{
    dfs_find(1);
    if(!gasit)
    {
        while(1)
            n=0;
    }
    while(!isanc(capete.first,capete.second))
    {
        cyc.push_back(capete.first);
        capete.first = parent[capete.first];
    }
    cyc.push_back(capete.first);
    vector<int> aux;
    while(capete.second!=capete.first)
    {
        aux.push_back(capete.second);
        capete.second = parent[capete.second];
    }
    reverse(aux.begin(),aux.end());
    for(auto x:aux)
        cyc.push_back(x);
    for(auto x:cyc)
        iscyc[x]=1;
    /*cout<<"cycle: ";
    for(auto x:cyc)
        cout<<x<<" ";
    cout<<"\n";*/
}
void dfs2(int nod, int par)
{
    maxd[nod] = depth[nod];
    cntmax[nod] = 1;
    vector<pair<int,int>> v;
    for(auto adj:con[nod])
    {
        if(adj!=par && !iscyc[adj])
        {
            depth[adj]=depth[nod]+1;
            dfs2(adj,nod);
            v.push_back({maxd[adj] - depth[nod], cntmax[adj]});
            if(maxd[adj]>maxd[nod])
            {
                maxd[nod] = maxd[adj];
                cntmax[nod] = cntmax[adj];
            }
            else if(maxd[adj]==maxd[nod])
                cntmax[nod] += cntmax[adj];
        }
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if((int)v.size()>1 && v[0].first + v[1].first >= maxdist)
    {
        if(v[0].first==v[1].first)
        {
            int cntpref = v[0].second;
            for(int i=1;i<v.size();i++)
            {
                if(v[i].first!=v[0].first)
                    break;
                if(2*v[0].first > maxdist)
                {
                    maxdist = 2*v[0].first;
                    cate = v[i].second * cntpref;
                }
                else if(2*v[0].first == maxdist)
                    cate += v[i].second * cntpref;
                cntpref += v[i].second;
            }
        }
        else
        {
            for(int i=1;i<v.size();i++)
            {
                if(v[i].first!=v[1].first)
                    break;
                if(v[0].first + v[1].first > maxdist)
                {
                    maxdist = v[0].first + v[1].first;
                    cate = v[i].second * v[0].second;
                }
                else if(v[0].first + v[1].first == maxdist)
                    cate += v[i].second * v[0].second;
            }
        }
    }
}
signed main()
{
    cin>>n;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        if(a==b)
        {
            while(1)
                n=0;
        }
        con[a].push_back(b);
        con[b].push_back(a);
    }
    find_cycle();
    for(int i=0;i<cyc.size();i++)
    {
        depth[cyc[i]]=0;
        dfs2(cyc[i],0);
        if(maxd[cyc[i]] > maxdist)
        {
            maxdist = maxd[cyc[i]];
            cate = cntmax[cyc[i]];
        }
        else if(maxd[cyc[i]] == maxdist)
            cate += cntmax[cyc[i]];
    }
    for(int i=0;i<cyc.size();i++)
    {
        for(int j=i+1;j<cyc.size();j++)
        {
            if(min(j-i, i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]] > maxdist)
            {
                maxdist = min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]];
                if(j-i != i + 1 + (int)cyc.size()-1-j) cate = cntmax[cyc[i]] * cntmax[cyc[j]];
                else cate = 2LL * cntmax[cyc[i]] * cntmax[cyc[j]];
            }
            else if(min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]] == maxdist)
            {
                if(j-i != i + 1 + (int)cyc.size()-1-j) cate += cntmax[cyc[i]] * cntmax[cyc[j]];
                else cate += 2LL * cntmax[cyc[i]] * cntmax[cyc[j]];
            }
        }
    }
   // cout<<"maxdist: "<<maxdist<<"\n";
    cout<<cate;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

shymbulak.cpp: In function 'void dfs2(long long int, long long int)':
shymbulak.cpp:110:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp:126:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:157:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:169:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:171:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for(int j=i+1;j<cyc.size();j++)
      |                       ~^~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50