Submission #167078

#	Time	Username	Problem	Language	Result	Execution time	Memory
167078		hentai_lover	Hard route (IZhO17_road)	C++14	52 / 100	1219 ms	99320 KiB

road

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#define fr(i, l, r) for(ll i = l; i <= r; ++ i)
#define rf(i, l, r) for(ll i = l; i >= r; -- i)

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef int ll;
typedef pair<ll, ll> pll;

const ll oo = ll(1e9) + 10;
const ll N = 5010;

ll f[N][N];
ll n, x, y, now;
vector <ll> g[N];
pll ans;

void dfs(ll x, ll s = 0, ll p = -1){
    f[now][x] = s;
    for(auto i : g[x])
        if(i != p){
            dfs(i, s + 1, x);
            f[now][x] = max(f[now][x], f[now][i]);
        }
}

void dfs2(ll x, ll s = 0, ll pp = -1, ll nw = 0){
    ll m1 = nw, m2 = nw;
    for(auto i : g[x])
        if(i != pp){
            if(m1 <= f[x][i])m2 = m1, m1 = f[x][i];
            else if(m2 <= f[x][i])m2 = f[x][i];
        }
    for(auto i : g[x]){
        if(i != pp){
            if(f[x][i] != m1){
                dfs2(i, s + 1, x, m1);
            }   else{
                dfs2(i, s + 1, x, m2);
            }
        }
    }
    //cout << "x = " << x << " nw = " << nw << " s = " << s << " now = " << now << endl;
    if(g[x].size() == 1 && s != 0){
        if(ans.first < nw * s)ans.first = nw * s, ans.second = 1;
        else if(ans.first == nw * s)ans.first = nw * s, ans.second ++;
    }

}

int main() {
    //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    fr(i, 2, n){
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    fr(i, 1, n){
        now = i;
        dfs(i);
    }

    fr(i, 1, n){
        if(g[i].size() == 1){
            now = i;
            dfs2(i);

        }
    }


    cout << ans.first << ' ' << ans.second / 2 << endl;
}


/*
3 3
1 5 1
2 3
1 3 5
2 3
*/

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 0 / 48