Submission #1116871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116871		kfhjad	Hard route (IZhO17_road)	C++17	0 / 100	4 ms	13648 KiB

road

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> adj[500001];
int up[500001], down[500001];
int upFreq[500001], downFreq[500001];
ll ans = 0;
int freq = 1;

void update(ll x, ll f)
{
    if (x > ans)
        ans = x, freq = f;
    else if (x == ans)
        freq += f;
}

void dfs(int node, int p)
{
    downFreq[node] = 1;
    
    for (int i : adj[node])
    {
        if (i == p)
            continue;
        
        dfs(i, node);
        
        if (down[node] < down[i] + 1)
            down[node] = down[i] + 1, downFreq[node] = downFreq[i];
        else if (down[node] == down[i] + 1)
            downFreq[node] += downFreq[i];
    }
}

void dfs1(int node, int p)
{
    
    vector<pair<ll, ll>> best;
    map<int, int> m;
    m[up[node]] += upFreq[node];
    vector<array<ll, 2>> paths;
    paths.push_back({up[node], upFreq[node]});
    
    for (int i : adj[node])
    {
        if (i == p)
            continue;
        
        m[down[i] + 1] += downFreq[i];
        paths.push_back({down[i] + 1, downFreq[i]});
        
        if (m.size() > 3)
            m.erase(m.begin());
    }
    
    for (auto [path, freq] : m) best.push_back({path, freq});
    
    best.resize(3);
    sort(best.rbegin(), best.rend());
    sort(paths.rbegin(), paths.rend());

    if (adj[node].size() > 2)
    {
        ll a = paths[0][0];
        ll b = paths[1][0];
        ll c = paths[2][0];
        ll cur_path_cnt = 0;
        ll x = a * (b + c);

        // all distinct
        if (a != b && b != c)
        {
            ll cnt = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
            
            update(x, paths[1][1] * cnt);
        }
        else if (a == b && b == c) // all same
        {
            ll cnt = 0;
            ll res = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
                    
            for (auto [len, f] : paths)
                if (len == c)
                    res += f * (cnt - f);
            
            update(x, res / 2);
        }
        else if (a == b) // only first two are the same
        {
            ll cnt = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
            
            update(x, (paths[0][1] + paths[1][1]) * cnt);
        }
        else if (b == c) // last two are the same
        {
            ll cnt = 0;
            ll res = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
                    
            for (auto [len, f] : paths)
                if (len == c)
                    res += f * (cnt - f);         
            
            update(x, res / 2);
        }
    }
    
    auto [m1, f1] = best[0];
    auto [m2, f2] = best[1];
    auto [m3, f3] = best[2];
    
    for (int i : adj[node])
    {
        if (i == p)
            continue;
        
        ll path = down[i] + 1;
        
        if (path == m1)
        {
            if (f1 == 1)
            {
                up[i] = m2 + 1;
                upFreq[i] = f2;
            }
            else
            {
                up[i] = m1 + 1;
                upFreq[i] = f1 - downFreq[i];
            }
        }
        else
        {
            up[i] = m1 + 1;
            upFreq[i] = f1;
        }
            
        dfs1(i, node);
    }
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N;
    cin >> N;
    
    while (--N)    
    {
        int a, b;
        cin >> a >> b;
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(1, 0);
    dfs1(1, 0);
    
    cout << ans << ' ' << freq << endl;
	
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs1(int, int)':
road.cpp:70:12: warning: unused variable 'cur_path_cnt' [-Wunused-variable]
   70 |         ll cur_path_cnt = 0;
      |            ^~~~~~~~~~~~
road.cpp:124:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  124 |     auto [m3, f3] = best[2];
      |          ^~~~~~~~

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