Submission #343925

#	Time	Username	Problem	Language	Result	Execution time	Memory
343925		Sprdalo	Hard route (IZhO17_road)	C++17	100 / 100	933 ms	144200 KiB

road

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 5e5+5;
vi e[maxn], p(maxn);
vp dp[maxn], d(maxn, {0,1});

void update_pi(pi& a, pi b){
    if (a.first == b.first)
        a.second += b.second;
    if (a.first < b.first)
        a = b;
}

pi dfs(int x, int st){
    pi q = {0, 1};
    for (auto& i : e[x]){
        if (i == st){
            p[x] = i;
            continue;
        }

        pi y = dfs(i, x);
        ++y.first;

        update_pi(q, y);

        dp[x].push_back(y);
    }

    if (q.first == 0)
        dp[x].push_back(q);

    return q;
}

void calc(int x){
    pi q = *max_element(dp[x].begin(), dp[x].end());

    pi t = q; t.second = 0;
    for (int i = 0; i < dp[x].size(); ++i){
        update_pi(t, dp[x][i]);
    }

    pi s = {0,1};
    for (int i = 0; i < dp[x].size(); ++i){
        if (dp[x][i].first == t.first) continue;
        update_pi(s, dp[x][i]);
    }

    int cur = 0;
    for (auto& i : e[x]){
        if (p[x] == i) continue;

        if (dp[x][cur].first == t.first && dp[x][cur].second == t.second){
            d[i] = d[x]; d[i].first++;
            if (s.first>0)
            update_pi(d[i], {s.first+1, s.second});
        } else {
            pi tmp = t;
            if (dp[x][cur].first == t.first)
                tmp.second -= dp[x][cur].second;
            d[i] = d[x]; d[i].first++;
            update_pi(d[i], {tmp.first+1, tmp.second});
        }

        calc(i);
        ++cur;
    }
}

pi sol = {0, 1};
void solve(int x){
    int len = dp[x].size();
    if ((len >= 2 && d[x].first > 0) || len >= 3){
        pi a = {0, 1}, b = {0,1}, c = {0, 1};
        dp[x].push_back(d[x]);

       // sort(dp[x].rbegin(), dp[x].rend());
        //a = dp[x][0]; b = dp[x][1]; c = dp[x][2];
        for (pi t : dp[x]){
            if (t.first > a.first){
                swap(b, c);
                swap(a, b);
                a = t;
                continue;
            }

            if (t.first > b.first){
                swap(b, c);
                b = t;
                continue;
            }

            if (t.first > c.first)
                c = t;
        }    

        int cnt = 0, cc = 0;
        for (pi t : dp[x]){
            if (t.first == c.first){
                ++cc;
                cnt += t.second;
            }
        }

        //cout << x << ' ' << a.first << ' ' << b.first << ' ' << c.first << ' ';
        pi res = {a.first * (b.first + c.first), 0};
        //if (res.first == 1980) cout << "BRATE " << a.first << ' ' << b.first << ' ' << c.first << ' ' << d[x].first << '\n';
        //cout << res.first << ' ';
        if (a.first == b.first && a.first == c.first){
            //if (res.first == 1152) cout << "PRVI\n";
            for (pi t : dp[x]){
                if (t.first != c.first) continue;
                res.second += t.second * (cnt - t.second);
            }
            //res.second *=2;
          //  res.second /= 3;
        }

        if (a.first == b.first && b.first != c.first){
            //if (res.first == 1152) cout << "DRUGI\n";
            res.second = (b.second+a.second) * cnt;
        }

        if (a.first != b.first && b.first == c.first){
            //if (res.first == 1152) cout << "TRECI\n";
            for (pi t : dp[x])
                if (t.first == c.first)
                    res.second += t.second * (cnt - t.second);
        }

        if (a.first != b.first && b.first != c.first){
            //if (res.first == 1152) cout << "CETRI\n";
            res.second = b.second * cnt;
            res.second *= 2;
        }

        res.second /= 2;
        //if (res.first == 2)
        //    cout <<res.second << '\n';
        //cout << res.second << '\n';
        update_pi(sol, res);
    }

    for (auto& i : e[x]){
        if (i != p[x])
            solve(i);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n;
    cin >> n;

    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;

        e[u].push_back(v);
        e[v].push_back(u);
    }

    dfs(1, 1);
    calc(1);
    solve(1);

    cout << sol.first << ' ' << sol.second << '\n';
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
*/

Compilation message (stderr)

road.cpp: In function 'void calc(ll)':
road.cpp:56:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < dp[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~
road.cpp:61:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < dp[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~

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