제출 #984993

#제출 시각아이디문제언어결과실행 시간메모리
984993a_l_i_r_e_z_aHard route (IZhO17_road)C++17
100 / 100
725 ms114232 KiB
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 5e5 + 5;
const int inf = 1e9 + 7;
ll n, cnt[maxn];
pll dpu[maxn], dpd[maxn];
pll ans = mp(0, 1);
vector<int> adj[maxn];

void smaxp(pll &x, pll y, int v){
    if(y.F + v > x.F) x = mp(y.F + v, y.S);
    else if(y.F + v == x.F) x.S += y.S;
}

void dfsd(int v = 1, int p = 0){
    dpd[v] = mp(0, 1);
    for(auto u: adj[v]) if(u != p){
        dfsd(u, v);
        smaxp(dpd[v], dpd[u], 1);
    }
}

void dfsu(int v = 1, int p = 0){
    int mx1 = -1, mx2 = -1;
    for(auto u: adj[v]) if(u != p){
        if(mx1 == -1 || dpd[u].F >= dpd[mx1].F){
            mx2 = mx1;
            mx1 = u;
        }
        else if(mx2 == -1 || dpd[u].F > dpd[mx2].F) mx2 = u;
        smaxp(dpu[u], dpu[v], 1);
    }
    for(auto u: adj[v]) if(u != p){
        if(u == mx1){
            if(mx2 != -1){
                smaxp(dpu[u], dpd[mx2], 2);
            }
        }
        else smaxp(dpu[u], dpd[mx1], 2);
        dfsu(u, v);
    }
}

void dfs(int v = 1, int p = 0){
    vector<pll> vec;
    for(auto u: adj[v]) if(u != p){
        dfs(u, v);
        vec.pb(mp(dpd[u].F + 1, dpd[u].S));
    }
    if(v > 1) vec.pb(dpu[v]);
    if(vec.size() < 3) return;
    sort(all(vec), greater<>());
    ll val = vec[1].F + vec[2].F;
    ll res = 0;
    for(int i = 1; i < vec.size(); i++){
        res += vec[i].S * cnt[val - vec[i].F];
        cnt[vec[i].F] += vec[i].S;
    }
    if(vec[2].F == vec[0].F){
        for(int i = 1; i < vec.size() && vec[i].F == vec[0].F; i++){
            res += vec[i].S * vec[0].S;
        }
    }
    else if(vec[1].F == vec[0].F){
        res += (res / vec[1].S) * vec[0].S;
    }
    smaxp(ans, mp(vec[0].F * val, res), 0);
    for(auto u: vec) cnt[u.F] = 0;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfsd();
    for(int i = 1; i <= n; i++) dpu[i] = mp(0, 1);
    dfsu();
    // for(int i = 1; i <= n; i++){
    //     cout << i << ' ' << dpd[i].F << ' ' << dpd[i].S << ' ' << dpu[i].F << ' ' << dpu[i].S << '\n';
    // }
    dfs();
    cout << ans.F << ' ' << ans.S << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

road.cpp: In function 'void dfs(int, int)':
road.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 1; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
road.cpp:82:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i = 1; i < vec.size() && vec[i].F == vec[0].F; i++){
      |                        ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...