oj.uz

Submission #442736

# Submission time Handle Problem Language Result Execution time Memory
442736 2021-07-08T19:52:53 Z leaked Shymbulak (IZhO14_shymbulak) C++14
80 / 100
 172 ms 29496 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define vec vector
#define sz(x) ( int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
typedef unsigned long long ull;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=2e5+1;
vec<int> g[N];
int n;
int dst[N];
int used[N],pr[N];
vec<int>cyc;
//vec<int>g
void dfs(int v,int p){
    used[v]=1;
    for(auto &z : g[v]){
        if(z==p) continue;
        if(used[z]==1){
            int u=v;
            while(u!=z){
                cyc.pb(u);
                u=pr[u];
            }
            cyc.pb(u);
        }
        else if(!used[z]){
             pr[z]=v;
             dfs(z,v);
        }
    }
    used[v]=2;
}
pii ans=m_p(0,0);
pii dp[N];
void upd(pii &a,pii b){
    if(a.f<b.f) a=b;
    else if(a.f==b.f) a.s+=b.s;
}
void dfs2(int v,int p){
    vec<int>vc;
    dp[v]={0,1};
    for(auto &z : g[v]){
        if(used[z] || z==p) continue;
        dfs2(z,v);
        upd(dp[v],{dp[z].f+1,dp[z].s});
        vc.pb(z);
    }
    int m=sz(vc);
    vec<pii>pref(m),suf(m);
    pii me={0,0};
    for(int i=0;i<m;i++){
        int z=vc[i];
        pref[i]=me;
        upd(me,{dp[z].f+1,dp[z].s});
    }
    for(int i=0;i<m;i++){
        pii x=pref[i];
        if(x.f==0) x.s=1;
        upd(ans,m_p(dp[vc[i]].f+1+x.f,1ll*x.s*dp[vc[i]].s));
    }
}
struct myset{
    map<int,int>mp;
    int ad=0;
    void add(pii x){
        x.f-=ad;
        mp[x.f]+=x.s;
    }
    void del(pii x){
        x.f-=ad;
        mp[x.f]-=x.s;
        if(!mp[x.f]) mp.erase(x.f);
    }
    pii get(){
        pii x={-3*N,-1};
        if(sz(mp)){
            x=*mp.rbegin();
        }
        x.f+=ad;
        return x;
    }
}f,s;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    dfs(0,0);
    fill(used,used+n,0);
    for(auto &z : cyc) used[z]=1;
    for(auto &z : cyc){
        dfs2(z,z);
    }
//    cerr<<ans.f<<' '<<ans.s<<endl;
    int l=sz(cyc)/2;
//    cout<<l<<endl;
    for(int i=0;i<sz(cyc);i++){
        int v=cyc[i];
        if(i>l){
            s.add({dp[v].f+sz(cyc)-i,dp[v].s});
        }
        else{
            f.add({dp[v].f+i,dp[v].s});
        }
    }
    auto dst=[&](int i,int j){
        int x=(i-j+sz(cyc))%sz(cyc);
        return min(x,sz(cyc)-x);
    };
    for(int i=0;i<sz(cyc);i++){
        int v=cyc[i];
        f.del(dp[v]);
//        cerr<<<<' '<<dp[i].f<<' '<<f.get().f<<' '<<s.get().f<<endl;
        pii me=f.get();
        upd(ans,{me.f+dp[v].f,1ll*me.s*dp[v].s});
        if(sz(cyc)%2==0){
            int u=cyc[(i+l)%2];
            pii x={dp[u].f+dp[v].f,1ll*dp[u].s*dp[u].s};
            upd(ans,x);
        }
        int j=(i+l+1)%sz(cyc);
        int u=cyc[j];
        s.del({dp[u].f+dst(i,j),dp[u].s});
        s.add(dp[v]);
        s.ad++;
        f.ad--;
        f.add({dp[u].f+dst((i+1)%sz(cyc),j),dp[u].s});
    }
//    cout<<ans.f<<' '<<ans.s<<endl;
    cout<<ans.s;
    return 0;
}

/*
5
1 2
2 3
3 4
4 5
5 1
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 5032 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 5028 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 3 ms 5068 KB Output is correct
15 Correct 3 ms 5036 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 4 ms 5032 KB Output is correct
3 Correct 4 ms 5164 KB Output is correct
4 Incorrect 4 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13100 KB Output is correct
2 Correct 68 ms 13316 KB Output is correct
3 Correct 75 ms 20192 KB Output is correct
4 Correct 63 ms 13000 KB Output is correct
5 Correct 64 ms 13072 KB Output is correct
6 Correct 172 ms 20676 KB Output is correct
7 Correct 113 ms 16708 KB Output is correct
8 Correct 126 ms 21052 KB Output is correct
9 Correct 105 ms 21232 KB Output is correct
10 Correct 95 ms 22336 KB Output is correct
11 Correct 99 ms 28212 KB Output is correct
12 Correct 109 ms 29496 KB Output is correct