oj.uz

Submission #580567

# Submission time Handle Problem Language Result Execution time Memory
580567 2022-06-21T12:39:49 Z FatihSolak Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 129 ms 30348 KB 
#include <bits/stdc++.h>
#define N 200005
#define int long long
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],2*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
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 6 ms 5420 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 4 ms 5404 KB Output is correct
10 Correct 5 ms 5312 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 12104 KB Output is correct
2 Correct 64 ms 12932 KB Output is correct
3 Correct 86 ms 30348 KB Output is correct
4 Correct 36 ms 12548 KB Output is correct
5 Correct 33 ms 12032 KB Output is correct
6 Correct 124 ms 19820 KB Output is correct
7 Correct 98 ms 17768 KB Output is correct
8 Correct 68 ms 21672 KB Output is correct
9 Correct 70 ms 20680 KB Output is correct
10 Correct 75 ms 25128 KB Output is correct
11 Correct 88 ms 22152 KB Output is correct
12 Correct 129 ms 23056 KB Output is correct