oj.uz

Submission #580569

# Submission time Handle Problem Language Result Execution time Memory
580569 2022-06-21T12:40:47 Z FatihSolak Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 143 ms 26984 KB 
#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],2ll*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 4 ms 4948 KB Output is correct
3 Correct 4 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 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4984 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 4 ms 5204 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 5 ms 5308 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9708 KB Output is correct
2 Correct 44 ms 10316 KB Output is correct
3 Correct 79 ms 26984 KB Output is correct
4 Correct 34 ms 10404 KB Output is correct
5 Correct 35 ms 10248 KB Output is correct
6 Correct 143 ms 14164 KB Output is correct
7 Correct 97 ms 12400 KB Output is correct
8 Correct 63 ms 15324 KB Output is correct
9 Correct 65 ms 14784 KB Output is correct
10 Correct 68 ms 17496 KB Output is correct
11 Correct 84 ms 15424 KB Output is correct
12 Correct 103 ms 16000 KB Output is correct