Submission #170215

#	Time	Username	Problem	Language	Result	Execution time	Memory
170215		andrew	Hard route (IZhO17_road)	C++17	52 / 100	2037 ms	131012 KiB

road

#include <bits/stdc++.h>

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

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6;
const ll inf = 3e18;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}

vector <ll> v[MAXN];
bool is_leaf[MAXN];
vector <ll> leaves;
ll Mx[MAXN], kol[MAXN];

ll mx = 0, ans = 0;

void build(ll x, ll pr = 0){
    Mx[x] = 0;
    kol[x] = 1;
    for(auto to : v[x])if(to != pr){
        build(to, x);
        Mx[x] = max(Mx[x], Mx[to] + 1);
        kol[x] += kol[to];
    }
}

void calc(ll x, ll pr = 0, ll Sum = 0, ll deep = 0){
    ll mb = 0;
    if(is_leaf[x] && pr != 0){
        ll t = deep * Sum;
        if(t > mx){
            mx = t;
            ans = 0;
        }
        if(mx == t)ans++;
        return;
    }

    vector <ll> ver, suf, pref;

    for(auto to : v[x])if(to != pr){
        ver.p_b(to);
    }

    ll nn = sz(ver);
    pref.resize(nn);
    suf.resize(nn);

    for(int i = 0; i < nn; i++){
        pref[i] = max(Mx[ver[i]] + 1, (i == 0 ? 0 : pref[i - 1]));
    }

    for(int i = nn - 1; i >= 0; i--){
        suf[i] = max(Mx[ver[i]] + 1, (i == nn - 1 ? 0 : suf[i + 1]));
    }

    for(int i = 0; i < nn; i++){
        calc(ver[i], x, max(Sum, max((i == 0 ? 0 : pref[i - 1]), (i == nn - 1 ? 0 : suf[i + 1]))), deep + 1);

    }

}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL


    ll n;

    cin >> n;

    for(int i = 1; i < n; i++){
        ll a, b;
        cin >> a >> b;
        v[a].p_b(b);
        v[b].p_b(a);
    }

    for(int i = 1; i <= n; i++){
        if(sz(v[i]) == 1){
            is_leaf[i] = 1;
            leaves.p_b(i);
        }
    }

    for(auto root : leaves){
        build(root);
        calc(root);
    }

    cout << mx << " " << ans / 2 << "\n";

    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void calc(ll, ll, ll, ll)':
road.cpp:47:8: warning: unused variable 'mb' [-Wunused-variable]
     ll mb = 0;
        ^~

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