답안 #883667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883667 2023-12-05T16:26:54 Z alexdd 관광지 (IZhO14_shymbulak) C++17
100 / 100
131 ms 28476 KB
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int INF = 1e9;
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;
int imp2(int x)
{
    if(x<0)
        return -1;
    return x/2;
}
pair<int,int> aint[530000][2];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    if(x.first > y.first)
        return x;
    if(x.first < y.first)
        return y;
    return {x.first, y.second + x.second};
}
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod][0] = {maxd[cyc[st]]-st, cntmax[cyc[st]]};
        aint[nod][1] = {maxd[cyc[st]]+st, cntmax[cyc[st]]};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod][0] = combine(aint[nod*2][0], aint[nod*2+1][0]);
    aint[nod][1] = combine(aint[nod*2][1], aint[nod*2+1][1]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri, int c)
{
    if(le>ri)
        return {-INF,-1};
    if(le==st && dr==ri)
        return aint[nod][c];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri),c),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,c));
}


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]];
        //cout<<i<<" "<<cyc[i]<<"   "<<maxd[cyc[i]]<<" "<<cntmax[cyc[i]]<<" zzz\n";
    }
    build(1,0,(int)cyc.size()-1);
    for(int i=1;i<cyc.size();i++)
    {
        pair<int,int> x = qry(1,0,(int)cyc.size()-1, max(0LL,imp2(2*i - (int)cyc.size() + 1)), i-1, 0);
        x.first += i + maxd[cyc[i]];
        if(x.first > maxdist)
        {
            maxdist = x.first;
            cate = x.second * cntmax[cyc[i]];
        }
        else if(x.first == maxdist)
            cate += x.second * cntmax[cyc[i]];
        //cout<<i<<" "<<cyc[i]<<"   "<<imp2(2*i - (int)cyc.size())<<" zzz\n";

        x = qry(1,0,(int)cyc.size()-1,0,min(i-1, imp2(2*i - (int)cyc.size())), 1);
        x.first += (int)cyc.size()-1-i + 1 + maxd[cyc[i]];
        if(x.first > maxdist)
        {
            maxdist = x.first;
            cate = x.second * cntmax[cyc[i]];
        }
        else if(x.first == maxdist)
            cate += x.second * cntmax[cyc[i]];
    }
    //cout<<"maxdist: "<<maxdist<<"\n";
    cout<<cate;
    return 0;
}
/**

2*i < 2*j + cyc.size()
2*j > 2*i - cyc.size()


*/

Compilation message

shymbulak.cpp: In function 'void dfs2(long long int, long long int)':
shymbulak.cpp:152: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]
  152 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp:168: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]
  168 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:199: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]
  199 |     for(int i=0;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
shymbulak.cpp:213: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]
  213 |     for(int i=1;i<cyc.size();i++)
      |                 ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14768 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14928 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14680 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 2 ms 14940 KB Output is correct
15 Correct 3 ms 14936 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 15168 KB Output is correct
7 Correct 5 ms 14940 KB Output is correct
8 Correct 5 ms 14940 KB Output is correct
9 Correct 5 ms 14896 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 18952 KB Output is correct
2 Correct 62 ms 18756 KB Output is correct
3 Correct 65 ms 25548 KB Output is correct
4 Correct 55 ms 18516 KB Output is correct
5 Correct 55 ms 18664 KB Output is correct
6 Correct 131 ms 22444 KB Output is correct
7 Correct 87 ms 20304 KB Output is correct
8 Correct 117 ms 22356 KB Output is correct
9 Correct 119 ms 22356 KB Output is correct
10 Correct 115 ms 25172 KB Output is correct
11 Correct 110 ms 28476 KB Output is correct
12 Correct 116 ms 28064 KB Output is correct