Submission #1015987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015987		codefox	Hard route (IZhO17_road)	C++14	100 / 100	733 ms	242624 KiB

road

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

vector<vector<int>> graph;
vector<pii> depth;
pii sol = {0,0};

void add(pii p, pii &s)
{
    if (p.first > s.first)
    {
        s = p;
    }
    else if (p.first == s.first)
    {
        s.second += p.second;
    }
}

void dfsup(int i, int p, pii d)
{
    vector<pii> conn;
    vector<pii> conns;
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        pii m = depth[ele];
        conn.push_back(m);
        conns.push_back(m);
    }
    int b = 0;
    if (conns.empty())
    {
        b = 1;
        conns.push_back({0, 1});
        conn.push_back({0, 1});
    }
    if (d.second) conns.push_back(d);
    if (d.second) conn.push_back(d);
    sort(conns.begin(), conns.end(), greater<pii>());
    #define arr array<int, 4>
    vector<arr> conns2;
    arr curr = {conns[0].first, 1, conns[0].second, 0};
    for (int j = 1; j < conns.size(); j++)
    {
        pii ele = conns[j];
        if (ele.first == curr[0])
        {
            curr[3] += ele.second*curr[2];
            curr[2] += ele.second;
            curr[1]++;
        }
        else
        {
            conns2.push_back(curr);
            curr = {{ele.first, 1, ele.second, 0}};
        }
    }
    conns2.push_back(curr);
    int j = 0;
    for (int ele:graph[i])
    {
        if (ele==p) continue;
        pii pp = {conns2[0][0], conns2[0][2]};
        if (pp.first == conn[j].first) pp.second -= conn[j].second;
        if (pp.second == 0) pp = {conns2[1][0], conns2[1][2]};
        pp.first++;
        dfsup(ele, i, pp);
        j++;
    }
    for (pii ele:conn)
    {
        int k = 0;
        arr p1 = conns2[k];
        int y = (p1[1]>2);
        if (p1[0] == ele.first && p1[1]<=2)
        {
            p1[1]--;
            p1[2]-=ele.second;
            p1[3]-= ele.second*p1[2];
        }
        if (p1[1] == 0)
        {
            k++;
            p1 = conns2[k];
        }
        if (p1[1]>1)
        {
            add({p1[0]*2*ele.first, p1[3]}, sol);
            if (y) break;
            continue;
        }
        k++;
        if (k==conns2.size())
        {
            if (b && p1[0]) add({p1[0]*ele.first, p1[2]}, sol);
            continue;
        }
        arr p2  = conns2[k];
        if (p2[0] == ele.first)
        {
            p2[1]--;
            p2[2]-=ele.second;
            p2[3]-= ele.second*p2[2];
        }
        if (p2[1] == 0)
        {
            k++;
            p2 = conns2[k];
        }
        if (k==conns2.size())
        {
            if (b && p1[0]) add({p1[0]*ele.first, p1[2]}, sol);
            continue;
        }
        add({ele.first*(p1[0]+p2[0]), p1[2]*p2[2]}, sol);
    }
}

pii dfsdown(int i, int p)
{
    pii mx = {0,0};
    if (graph[i].size()==1 && p >= 0) mx = {0, 1};
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        pii m = dfsdown(ele, i);
        add(m, mx);
    }
    mx.first++;
    depth[i] = mx;
    return mx;
}

int32_t main()
{
    int n;
    cin >> n;
    if (n==2)
    {
        cout << 0 << " " << 1;
        return 0;
    }

    graph.assign(n, vector<int>());
    depth.assign(n, {0,0});

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int start = 0;
    for (int i = 0; i < n; i++)
    {
        if (graph[i].size()>1) start = i;
    }

    dfsdown(start, -1);
    dfsup(start, -1, {0,0});


    //get rid of double counting!

    if (sol.first==0) cout << 0 << " " << 1;
    else cout << sol.first << " " << sol.second;
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfsup(long long int, long long int, std::pair<long long int, long long int>)':
road.cpp:48:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int j = 1; j < conns.size(); j++)
      |                     ~~^~~~~~~~~~~~~~
road.cpp:98:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         if (k==conns2.size())
      |             ~^~~~~~~~~~~~~~~
road.cpp:115:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         if (k==conns2.size())
      |             ~^~~~~~~~~~~~~~~

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