Submission #1130018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130018		DaciejMaciej	Hard route (IZhO17_road)	C++20	0 / 100	15 ms	19896 KiB

road

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

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;

template <class T>

using VV = vector<vector<T>>;

using VI = vector<int>;
using VVI = vector<vector<int>>;

using VL = vector<long long>;
using VVL = vector<vector<long long>>;

using VC = vector<char>;
using VVC = vector<vector<char>>;

using VB = vector<bool>;
using VVB = vector<vector<bool>>;

using VD = vector<double>;
using VVD = vector<vector<double>>;

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using PIL = pair<int, long long>;
using PLI = pair<long long, int>;

using VPII = vector<pair<int, int>>;
using VPLL = vector<pair<long long, long long>>;

#define LINE '\n'
#define SPACE ' '
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i < (int(b)); i++)
#define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sq(a) ((a) * (a))
#define sz(x) ((int)x.size())

#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr)
#define debug(x) cerr << #x << " = " << x << endl;

const ll MOD = 1e9 + 7;

template <class T>
inline void maxi(T &a, T b)
{
    a = max(a, b);
}

template <class T>
inline void mini(T &a, T b)
{
    a = min(a, b);
}

template <class T>
inline void addi(T &a, T b)
{
    a = (a + b) % MOD;
}

template <class T>
inline void subi(T &a, T b)
{
    a = (a - b + MOD) % MOD;
}

template <class T>
inline T add(T a, T b)
{
    return (a + b) % MOD;
}

template <class T>
inline T sub(T a, T b)
{
    return (a - b + MOD) % MOD;
}

template <class T>
inline T mul(T a, T b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}

constexpr ll binpow(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

const int INF = 1e9;

const int MAX_N = 5e5 + 3;

int n;

VL dp(MAX_N, 0); // max dist down
VL ct(MAX_N, 1); // no of ways

VI g[MAX_N];

void dfs1(int c, int p)
{
    for (auto v : g[c])
    {
        if (v == p)
            continue;
        dfs1(v, c);

        if (dp[v] + 1 > dp[c])
        {
            dp[c] = dp[v] + 1;
            ct[c] = ct[v];
        }
        else if (dp[v] + 1 == dp[c])
        {
            ct[c] += ct[v];
        }
    }
}

ll ans_dist = 0;
ll ans_ct = 0;
void dfs2(int c, int p, int up_dist, int up_ways)
{
    // debug(c);
    // debug(up_dist);
    // debug(dp[c]);
    // debug(ct[c]);
    // cerr << LINE;
    vector<PLL> vec;
    if(c != 1)
    vec.PB({up_dist, up_ways});

    for (auto v : g[c]) {
        if(v != p) vec.PB({dp[v] + 1, ct[v]});
    }
        

    sort(RALL(vec));

    if (sz(g[c]) >= 3)
    {
        ll dist = vec[0].first * (vec[1].first + vec[2].first);
        
        ll ways = 0;
        ll eq = 0; // sum of ways to get vec[2].dist
        for (auto [d, w] : vec)
        {
            // debug(d);
            // debug(w);
            if (d == vec[2].first)
                eq += w;
        }

        if (vec[1].first == vec[2].first)
        {
            // since vec[0] is the max dist, 1 and 2 are terminals
            ways = eq * eq;
            
            for (auto [d, w] : vec)
            {
                // delete duplicates(paths overlap)
                if (d == vec[2].first)
                    ways -= sq(w);
            }

            // we need unique paths, (a, b) is the same as (b, a)
            ways /= 2;
        }
        else if (vec[0].first == vec[1].first)
        {
            ways = eq * (vec[0].second + vec[1].second);
        }
        else
        {
            ways = vec[1].second * eq;
        }

        if (dist > ans_dist) {
            ans_dist = dist;
            ans_ct = ways;
        }
            
        else if (dist == ans_dist)
            ans_ct += ways;
    }

    auto [d1, w1] = vec[0];
   
    ll d2 = 0, w2 = 0;
    if (sz(g[c]) >= 2)
    {
        auto [d2, w2] = vec[1];
    }

    w1 = w2 = 0;

    for (auto [d, w] : vec)
    {
        if (d1 == d)
            w1 += w;
        if (d2 == d)
            w2 += w;
    }
    maxi(w1, 1LL);
    maxi(w2, 1LL);

    
    for (auto v : g[c])
    {
        if (v == p)
            continue;

        if (dp[v] + 1 == d1)
        { // max paths goes trough
            if (ct[v] == w1)
            {
                dfs2(v, c, d2 + 1, w2);
            }
            else {
                dfs2(v, c, d1 + 1, w1 - ct[v]);   
            }
                
        }
        else
        {
            dfs2(v, c, d1 + 1, w1);
        }

        
    }
}

void solve()
{
    cin >> n;
    FOR(i, 0, n - 1)
    {
        int a, b;
        cin >> a >> b;
        
        g[a].PB(b);
        g[b].PB(a);
    }

    dfs1(1, 1);
    dfs2(1, 1, 0, 1);

    if (ans_dist == 0)
        ans_ct = 1;
    cout << ans_dist << SPACE << ans_ct << LINE;
}

int main()
{
    fastio();

    int t = 1;
    // cin >> t;

    while (t--)
        solve();
}

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