oj.uz

답안 #580569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580569 2022-06-21T12:40:47 Z FatihSolak 관광지 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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