제출 #883667

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

shymbulak

#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()


*/

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

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++)
      |                 ~^~~~~~~~~~~

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