답안 #883643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883643 2023-12-05T15:26:54 Z alexdd 관광지 (IZhO14_shymbulak) C++17
0 / 100
67 ms 18980 KB
#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
        {
            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],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());
    for(int i=0;i<v.size();i++)
        v[i].first = -v[i].first;
    if((int)v.size()>1 && v[0].first + v[1].first >= maxdist)
    {
        if(v[0].first==v[1].first)
        {
            int ult = (int)v.size()-1;
            for(int i=1;i<v.size();i++)
            {
                if(v[i]!=v[0])
                {
                    ult = i-1;
                    break;
                }
            }
            int cntpref=v[0].second;
            for(int i=1;i<=ult;i++)
            {
                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
        {
            int ult = (int)v.size()-1;
            for(int i=2;i<v.size();i++)
            {
                if(v[i]!=v[1])
                {
                    ult = i-1;
                    break;
                }
            }
            for(int i=1;i<=ult;i++)
            {
                if(v[0].first + v[1].first > maxdist)
                {
                    maxdist = v[0].first + v[1].first;
                    cate = v[i].second * v[0].second;
                }
                else if(2*v[0].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;
        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;
}

Compilation message

shymbulak.cpp: In function 'void dfs2(long long int, long long int)':
shymbulak.cpp:99:18: 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]
   99 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
shymbulak.cpp:106: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]
  106 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp:130: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]
  130 |             for(int i=2;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:162: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]
  162 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:174: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]
  174 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:176: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]
  176 |         for(int j=i+1;j<cyc.size();j++)
      |                       ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Incorrect 3 ms 14684 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 4 ms 14740 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Incorrect 3 ms 14684 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 18980 KB Output isn't correct
2 Halted 0 ms 0 KB -