답안 #883652

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

Compilation message

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:138: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]
  138 |             for(int i=0;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp:140:32: 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]
  140 |                 for(int j=i+1;j<v.size();j++)
      |                               ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:170: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]
  170 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:182: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]
  182 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:184: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]
  184 |         for(int j=i+1;j<cyc.size();j++)
      |                       ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14492 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14736 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14680 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
# 결과 실행 시간 메모리 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 14684 KB Output is correct
5 Correct 6 ms 14940 KB Output is correct
6 Correct 5 ms 15196 KB Output is correct
7 Correct 5 ms 14940 KB Output is correct
8 Correct 5 ms 14940 KB Output is correct
9 Correct 7 ms 14948 KB Output is correct
10 Correct 5 ms 14940 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 18892 KB Output is correct
2 Correct 60 ms 18772 KB Output is correct
3 Correct 1461 ms 21204 KB Output is correct
4 Correct 64 ms 19536 KB Output is correct
5 Correct 65 ms 19804 KB Output is correct
6 Correct 135 ms 24656 KB Output is correct
7 Correct 92 ms 22100 KB Output is correct
8 Correct 117 ms 24788 KB Output is correct
9 Correct 131 ms 24660 KB Output is correct
10 Correct 138 ms 25596 KB Output is correct
11 Correct 113 ms 29464 KB Output is correct
12 Correct 128 ms 29812 KB Output is correct