Submission #1189616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189616		stefanopulos	Hard route (IZhO17_road)	C++20	100 / 100	494 ms	73404 KiB

road

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ldb;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;

#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
 
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 500005; 

int n;

vector<int> g[mxN];

int d[mxN];
int par[mxN];
void dfs1(int v, int p){
    par[v] = p;
    for(auto u : g[v]){
        if(u != p){
            d[u] = d[v] + 1; dfs1(u, v); 
        }
    }
}

pll cmb(pll s1, pll s2){
    if(s1.fi == s2.fi)return {s1.fi, s1.se + s2.se};
    else return (s1.fi > s2.fi ? s1 : s2);
}

pll rez = {0, 0};

pii mx[mxN];
bool visited[mxN];
void dfs2(int v, int p, int dist){

    if(sz(g[v]) == 1){
        mx[v] = {d[v], 1};
        return;
    }

    pii najv1 = {-inf, 0}, najv2 = {-inf, 0}; mx[v] = {0, 0};
    for(auto u : g[v]){
        if(u == p || visited[u])continue;
          
        d[u] = d[v] + 1;  
        dfs2(u, v, dist);

        if(mx[u].fi > najv1.fi){
            najv2 = najv1;
            najv1 = mx[u];
        }
        else if(mx[u].fi == najv1.fi)najv1.se += mx[u].se;
        else if(mx[u].fi > najv2.fi){
            najv2 = mx[u];
        }else if(mx[u].fi == najv2.se)najv2.se += mx[u].se;

        mx[v] = cmb(mx[v], mx[u]);

    }

    if(najv1.se > 1){
        pll sad = {1ll * (dist + d[v]) * (2 * najv1.fi - 2 * d[v]), 1ll * najv1.se * (najv1.se - 1) / 2};
        rez = cmb(rez, sad);
    }
    else if(najv2.se > 0){
        pll sad = {1ll * (dist + d[v]) * (najv1.fi + najv2.fi - 2 * d[v]), 1ll * najv1.se * najv2.se};
        rez = cmb(rez, sad);
    }

}

int pref[mxN];
int sufi[mxN];

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    ff(i,1,n - 1){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    d[1] = 0; dfs1(1, -1); int a = -1; ff(i,1,n)if(a == -1 || d[a] < d[i])a = i;
    d[a] = 0; dfs1(a, -1); int b = -1; ff(i,1,n)if(b == -1 || d[b] < d[i])b = i;

    int dia = d[b];

    vector<int> put;
    for(int i = b; i != -1; i = par[i])put.pb(i);

    for(auto c : put){
        visited[c] = 1;
    }

    int len = sz(put);
    ff(i,0,len - 1){
        int v = put[i];        
        d[v] = 0; dfs2(v, -1, max(i, len - i - 1));
    }

    ff(i,0,len - 1){
        int v = put[i];
        pref[i] = (mx[v].fi == i ? mx[v].se : 0) + (i == 0 ? 0 : pref[i - 1]);
    }

    fb(i,len - 1,0){
        int v = put[i];
        sufi[i] = (mx[v].fi == len - i - 1 ? mx[v].se : 0) + (i == len - 1 ? 0 : sufi[i + 1]);
    }

    int najv = 0;
    ff(i,0,len - 1){
        int v = put[i];
        najv = max(najv, mx[v].fi);
    }

    if(najv == 0){
        cout << 0 << " " << 1 << '\n';
        return 0;
    }

    rez = cmb(rez, make_pair(1ll * dia * najv, 1ll * pref[najv - 1] * sufi[len - najv]));
    ff(i,najv,len - najv - 1){
        int v = put[i];
        if(mx[v].fi == 0)continue;

        if(i <= len - i - 1){

            ll distL = 1ll * (i + mx[v].fi) * (len - i - 1);
            ll brL = 1ll * mx[v].se * pref[i - 1];
            rez = cmb(rez, make_pair(distL, brL));

            ll distR = 1ll * (len - i - 1 + mx[v].fi) * i;
            ll brR = 1ll * mx[v].se * (len - i - 1 == i ? sufi[len - i] : sufi[len - i - 1]);
            rez = cmb(rez, make_pair(distR, brR));

        }
        else{

            ll distR = 1ll * (i + mx[v].fi) * (len - i - 1);
            ll brR = 1ll * mx[v].se * pref[(len - i - 1) - 1];
            rez = cmb(rez, make_pair(distR, brR));

            ll distL = 1ll * (len - i - 1 + mx[v].fi) * i;
            ll brL = 1ll * mx[v].se * sufi[i + 1];
            rez = cmb(rez, make_pair(distL, brL));

        }

    }

    cout << rez.fi << " " << rez.se << '\n';

    return 0;
}
/*

7
1 2
1 3
2 4
2 5
3 6
3 7

4
1 2
2 3
2 4

5
1 2
2 3
3 4
4 5

// probati bojenje sahovski
*/
 
 
 
 
 

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