oj.uz

답안 #476687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476687 2021-09-28T08:06:14 Z ogibogi2004 관광지 (IZhO14_shymbulak) C++14
0 / 100
 96 ms 10624 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
int par[MAXN],n,depth[MAXN];
vector<int>g[MAXN];
vector<int>cycle;
bool vis[MAXN];
bool found;
int x1,x2;
int cycle_size;
void find_cycle(int u,int p)
{
    par[u]=p;
    for(auto xd:g[u])
    {
        if(par[xd]==0)
        {
            depth[xd]=depth[u]+1;
            find_cycle(xd,u);
        }
        else
        {
            x1=u;
            x2=xd;
        }
    }
}
void make_cycle()
{
    if(depth[x1]<depth[x2])swap(x1,x2);
    cycle.push_back(x1);
    for(;;)
    {
        x1=par[x1];
        cycle.push_back(x1);
        if(x1==x2)break;
    }
}
pair<int,int> maxd[MAXN];
pair<int,int> calc(int u)
{
    vis[u]=1;
    pair<int,int> ret={0,1};
    for(auto xd:g[u])
    {
        if(vis[xd])continue;
        pair<int,int> f=calc(xd);
        f.first++;
        if(f.first==ret.first)ret.second+=f.second;
        else if(f.first>ret.first)ret=f;
    }
    return maxd[u]=ret;
}
pair<int,int>maxdist;
int ans;
int val1[MAXN],val2[MAXN];
map<int,int> mp1,mp2;
int main()
{
    maxdist={0,0};
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    find_cycle(1,-1);
    make_cycle();
    cycle_size=cycle.size();
    for(int i=0;i<cycle_size;i++)
    {
        cycle.push_back(cycle[i]);
    }
    int t=cycle_size/2;
    for(int i=1;i<=cycle_size;i++)
    {
        vis[cycle[i]]=1;
    }
    for(int i=1;i<=cycle_size;i++)
    {
        calc(cycle[i]);
    }
    set<int>s1,s2;
    for(int i=0;i<cycle_size*2;i++)
    {
        val1[i]=-i+maxd[cycle[i]].first;
        val2[i]=i+maxd[cycle[i]].first;
    }
    for(int i=0;i<t;i++)
    {
        s1.insert(val1[i]);
        mp1[val1[i]]+=maxd[cycle[i]].second;
        s2.insert(val2[t+1+i]);
        mp2[val2[i]]+=maxd[cycle[t+1+i]].second;
    }
    int max1=(*s1.rbegin()),max2=(*s2.rbegin());
    int cnt,dist;
    cnt=mp1[max1]*maxd[cycle[t]].second;
    dist=max1+t+maxd[cycle[t]].first;
    if(dist>maxdist.first)
    {
        maxdist.first=dist;
        maxdist.second=0;
    }
    if(dist==maxdist.first)
    {
        maxdist.second+=cnt;
    }
    cnt=mp2[max2]*maxd[cycle[t]].second;
    dist=max2-t+maxd[cycle[t]].first;
    if(dist>maxdist.first)
    {
        maxdist.first=dist;
        maxdist.second=0;
    }
    if(dist==maxdist.first)
    {
        maxdist.second+=cnt;
    }
    for(int mid=t+1;mid+t<2*cycle_size;mid++)
    {
        s1.erase(val1[mid-t-1]);
        mp1[val1[mid-t-1]]-=maxd[cycle[mid-t-1]].second;
        s2.erase(val2[mid]);
        mp2[val2[mid]]-=maxd[cycle[mid]].second;
        s1.insert(val1[mid-1]);
        mp1[val1[mid-1]]+=maxd[cycle[mid-1]].second;
        s2.insert(val2[mid+t]);
        mp2[val2[mid+t]]+=maxd[cycle[mid+t]].second;
        max1=(*s1.rbegin());max2=(*s2.rbegin());
        cnt=mp1[max1]*maxd[cycle[mid]].second;
        dist=max1+t+maxd[cycle[mid]].first;
        if(dist>maxdist.first)
        {
            maxdist.first=dist;
            maxdist.second=0;
        }
        if(dist==maxdist.first)
        {
            maxdist.second+=cnt;
        }
        cnt=mp2[max2]*maxd[cycle[mid]].second;
        dist=max2-mid+maxd[cycle[mid]].first;
        if(dist>maxdist.first)
        {
            maxdist.first=dist;
            maxdist.second=0;
        }
        if(dist==maxdist.first)
        {
            maxdist.second+=cnt;
        }
    }
    ans=maxdist.second;
    cout<<ans<<endl;
return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 10624 KB Output isn't correct
2 Halted 0 ms 0 KB -