oj.uz

Submission #442740

# Submission time Handle Problem Language Result Execution time Memory
442740 2021-07-08T20:02:40 Z leaked Shymbulak (IZhO14_shymbulak) C++14
80 / 100
 210 ms 27052 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;
        assert(mp[x.f]>=x.s);
        mp[x.f]-=x.s;
        if(!mp[x.f]) mp.erase(x.f);
    }
    pii get(){
        pii x={-1e9,-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);
    }
    assert(sz(cyc));
//    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=abs(i-j);
        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 3 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 4 ms 5068 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 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 5068 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5196 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Incorrect 3 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 83 ms 12028 KB Output is correct
2 Correct 86 ms 12312 KB Output is correct
3 Correct 77 ms 19008 KB Output is correct
4 Correct 49 ms 11776 KB Output is correct
5 Correct 51 ms 11836 KB Output is correct
6 Correct 210 ms 18460 KB Output is correct
7 Correct 117 ms 15116 KB Output is correct
8 Correct 105 ms 18628 KB Output is correct
9 Correct 130 ms 18756 KB Output is correct
10 Correct 98 ms 19724 KB Output is correct
11 Correct 110 ms 25908 KB Output is correct
12 Correct 117 ms 27052 KB Output is correct