Submission #36828

#	Time	Username	Problem	Language	Result	Execution time	Memory
36828		alenam0161	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	206 ms	30568 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;
#define ad push_back
const int N =200007;
vector<int> g[N],loop;
using ll=long long;
void add(pair<int,ll>& aa,pair<int,ll>bb){
    if(aa.first<bb.first)aa=bb;
    else if(aa.first==bb.first)aa.second+=bb.second;
}
pair<int,ll> ans;
int par[N];
bool used[N];
bool gta=false;
void dfs0(int v,int p){
    if(gta)return;
par[v]=p;
used[v]=true;
for(int to:g[v]){
    if(gta)return;
    if(to==p)continue;
    if(used[to]){
        int r=v;
        while(true){
            loop.ad(r);
            if(r==to)break;
            r=par[r];
        }
        gta=true;
        return;
    }
    else dfs0(to,v);
}
}
pair<int,ll> dfs_upd(int v,int p){
pair<int,ll> cur={0,1};
for(int to:g[v]){
    if(to==p)continue;
    if(used[to])continue;
    pair<int,ll> w=dfs_upd(to,v);
    w.first++;
    add(ans,{cur.first+w.first,cur.second*w.second});
    add(cur,w);
}
return cur;
}
pair<int,ll> dp[N];
int t=0;
pair<int,ll> Mx[N*4];
void build(int l,int r,int v){
if(l==r){
    Mx[v]=dp[l];
    return;
}
int m=(l+r)/2;
build(l,m,v+v);
build(m+1,r,v+v+1);
add(Mx[v],Mx[v+v]);
add(Mx[v],{(m-l+1)+Mx[v+v+1].first,Mx[v+v+1].second});
}
pair<int,ll> get(int l,int r,int v,int tl,int tr,int qan=0){
if(tl<=l&&r<=tr)
        return {Mx[v].first+qan,Mx[v].second};
int m=(l+r)/2;
pair<int,ll> e={0,0};
if(tl<=m)add(e,get(l,m,v+v,tl,tr,qan));
if(tr>m){
    add(e,get(m+1,r,v+v+1,tl,tr,qan+max(0,m-max(l,tl)+1)));
}
return e;
}
int main()
{
  //  freopen("input.txt","r",stdin);
 //   freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].ad(v);
        g[v].ad(u);
    }
    dfs0(1,1);
    memset(used,0,sizeof(used));
    for(int to:loop)used[to]=true;
    for(int to:loop){
       dp[t++]=dfs_upd(to,to);
    }
    for(int i=0;i<t;++i){
        dp[i+t]=dp[i];
    }
    int len=t+t;
    build(0,len,1);
    int erk=t/2;
    for(int i=0;i<t;++i){
        pair<int,ll> z=get(0,len,1,i+1,i+erk,1);
        z=max(dp[i],{dp[i].first+z.first,dp[i].second*z.second});
        add(ans,z);
    }
   // cout<<ans.first<<endl;
    cout<<ans.second<<endl;
    return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:81:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&u,&v);
                            ^

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