Submission #580553

#	Time	Username	Problem	Language	Result	Execution time	Memory
580553		FatihSolak	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	51 ms	9712 KiB

shymbulak

#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
bool on_cycle[N];
int par[N];
int vis[N];
int dep[N];
pair<int,int> maxi[N];
vector<int> cycle;
pair<int,long long> merge(pair<int,long long> a,pair<int,long long> b){
    pair<int,long long> ret = {0,0};
    ret.first = max(a.first,b.first);
    if(a.first == ret.first)ret.second += a.second;
    if(b.first == ret.first)ret.second += b.second;
    return ret;
}
pair<int,long long> merge2(pair<int,long long> a,pair<int,long long> b){
    return {a.first + b.first,a.second*b.second};
}
struct SegTree{
    vector<pair<int,long long>> t;
    int n;
    SegTree(int size){
        n = size;
        t.assign(4*n,{-1e9,0});
    }
    void upd(int v,int tl,int tr,int pos,pair<int,long long> val){
        if(tl == tr){
            t[v] = merge(t[v],val);
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm)
            upd(v*2,tl,tm,pos,val);
        else upd(v*2+1,tm+1,tr,pos,val);
        t[v] = merge(t[v*2],t[v*2+1]);
    }
    pair<int,long long> get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl)
            return {-1e9,0};
        if(l <= tl && tr <= r)
            return t[v];
        int tm = (tl + tr)/2;
        return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
    }
    void upd(int pos,pair<int,long long> val){
        upd(1,0,n,pos,val);
    }
    pair<int,long long> get(int l,int r){
        return get(1,0,n,l,r);
    }
};
void dfs(int v,int pr){
    vis[v] = 1;
    par[v] = pr;
    for(auto u:adj[v]){
        if(u == pr)continue;
        if(cycle.size())return;
        if(vis[u] == 1){
            while(1){
                on_cycle[v] = 1;
                cycle.push_back(v);
                if(u == v)break;
                v = par[v];
            }
        }
        if(cycle.size())return;
        dfs(u,v);
    }
    vis[v] = 2;
}
pair<int,long long> res;
void dfs1(int v,int pr){
    maxi[v] = {dep[v],1};
    for(auto u:adj[v]){
        if(u == pr || on_cycle[u])continue;
        dep[u] = dep[v] + 1;
        dfs1(u,v);
        res = merge(res,{maxi[v].first + maxi[u].first - 2*dep[v],maxi[v].second * maxi[u].second});
        maxi[v] = merge(maxi[v],maxi[u]);
    }
    res = merge(res,{maxi[v].first-dep[v],maxi[v].second});
}
pair<int,long long> get_diameter_and_count(int v){
    res = {0,0};
    dfs1(v,0);
    return res;
}
void solve(){
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    assert(cycle.size() >= 3);
    // for(auto u:cycle){
    //     cout << u << " ";
    // }
    // cout << endl;
    pair<int,long long> ans = {0,0};
    for(auto u:cycle){
        ans = merge(ans,get_diameter_and_count(u));
    }
    int sz = cycle.size();
    for(int i = 0;i<sz;i++){
        for(int j = 0;j<sz;j++){
            if(i == j)continue;
            //cout << cycle[i] << " " << cycle[j] << " " << maxi[cycle[i]].first + maxi[cycle[j]].first + min(abs(i-j),sz-abs(i-j)) << endl; 
            ans = merge(ans,{maxi[cycle[i]].first + maxi[cycle[j]].first + min(abs(i-j),sz-abs(i-j)),maxi[cycle[i]].second * maxi[cycle[j]].second});
            if(abs(i-j) == sz - abs(i-j))
                ans = merge(ans,{maxi[cycle[i]].first + maxi[cycle[j]].first + min(abs(i-j),sz-abs(i-j)),maxi[cycle[i]].second * maxi[cycle[j]].second});
        }
    }
    /*
    if(cycle.size() % 2){
        int half_sz = cycle.size()/2;
        int sz = cycle.size();
        SegTree t(2*sz);
        SegTree t2(2*sz);
        for(int i = 0;i<2*sz;i++){
            t.upd(i,{maxi[cycle[i%sz]].first + i,maxi[cycle[i%sz]].second});
        }
        for(int i = 0;i<2*sz;i++){
            t2.upd(i,{maxi[cycle[i%sz]].first - i,maxi[cycle[i%sz]].second});
        }
        for(int i = 0;i<sz;i++){
            pair<int,long long> nowl = t2.get(i + half_sz + 1,i + sz-1);
            nowl.first += i + sz;
            pair<int,long long> nowr = t.get(i+1,i+half_sz);
            nowr.first -= i;
            nowl = merge2(nowl,maxi[cycle[i]]);
            nowr = merge2(nowr,maxi[cycle[i]]);
            ans = merge(ans,nowl);
            ans = merge(ans,nowr);
        }
    }
    else{
        int half_sz = cycle.size()/2 - 1;
        int sz = cycle.size();
        SegTree t(2*sz);
        SegTree t2(2*sz);
        for(int i = 0;i<2*sz;i++){
            t.upd(i,{maxi[cycle[i%sz]].first + i,maxi[cycle[i%sz]].second});
        }
        for(int i = 0;i<2*sz;i++){
            t2.upd(i,{maxi[cycle[i%sz]].first - i,maxi[cycle[i%sz]].second});
        }
        for(int i = 0;i<sz;i++){
            pair<int,long long> nowl = t2.get(i + half_sz + 2,i + sz-1);
            nowl.first += i + sz;
            pair<int,long long> nowr = t.get(i+1,i+half_sz);
            nowr.first -= i;
            pair<int,long long> middle = {half_sz + 1 + maxi[cycle[(i+half_sz+1)%sz]].first,2*maxi[cycle[(i+half_sz+1)%sz]].second};
            nowl = merge2(nowl,maxi[cycle[i]]);
            nowr = merge2(nowr,maxi[cycle[i]]);
            middle = merge2(middle,maxi[cycle[i]]);
            ans = merge(ans,nowl);
            ans = merge(ans,nowr);
            ans = merge(ans,middle);
        }
    }*/
    cout << ans.second / 2 << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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