Submission #761137

#	Time	Username	Problem	Language	Result	Execution time	Memory
761137		PanosPask	Hard route (IZhO17_road)	C++14	0 / 100	1 ms	304 KiB

road

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

int N;
pair<ll, ll> ans;
vector<vector<int>> adj_list;

// Inside variables
int leafs = 0;
vector<pi> total_best;
vector<pi> first_inside;
vector<int> topkid;
vector<pi> second_inside;
vector<pi> third_inside;

// Outside variables
vector<pi> path_outside;

pi operator + (pi a, pi b)
{
    if (a.f > b.f)
        return a;
    if (b.f > a.f)
        return b;

    return mp(a.f, b.s + a.s);
}
pair<ll, ll> operator + (pair<ll, ll> a, pair<ll, ll> b)
{
    if (b.s <= 0)
        return a;
    if (a.s <= 0)
        return b;

    if (a.f > b.f)
        return a;
    if (b.f > a.f)
        return b;

    return mp(a.f, b.s + a.s);
}

void calculate_inside(int node, int par)
{
    pi p1 = mp(0, 0), p2 = mp(0, 0), p3 = mp(0, 0);
    if (adj_list[node].size() == 1) {
        p1.s = 1;
        leafs++;
    }

    total_best[node].s = 1;
    for (auto neigh : adj_list[node]) {
        if (neigh == par)
            continue;

        calculate_inside(neigh, node);

        if (p1.f == total_best[neigh].f + 1) {
            total_best[node].s++;
        }

        if (p1.f < total_best[neigh].f + 1) {
            topkid[node] = neigh;
            total_best[node].s = 1;

            p3 = p2;
            p2 = p1;
            p1 = mp(total_best[neigh].f + 1, total_best[neigh].s);
        }
        else if (p2.f < total_best[neigh].f + 1) {
            p3 = p2;
            p2 = mp(total_best[neigh].f + 1, total_best[neigh].s);
        }
        else if (p3.f < total_best[neigh].f + 1) {
            p3 = mp(total_best[neigh].f + 1, total_best[neigh].s);
        }
    }

    total_best[node].f = p1.f;
    first_inside[node] = p1;
    second_inside[node] = p2;
    third_inside[node] = p3;
}

void try_triplet(pi a, pi b, pi c)
{
    int p1, p2, p3;
    int c1, c2, c3;

    tie(p1, c1) = a;
    tie(p2, c2) = b;
    tie(p3, c3) = c;


    ll chances = (ll)c1 * c2 * c3;
    ans = ans + mp((ll)p1 * (p2 + p3), (ll)c2 * c3);
    ans = ans + mp((ll)p2 * (p1 + p3), (ll)c1 * c3);
    ans = ans + mp((ll)p3 * (p2 + p1), (ll)c2 * c1);
}

void calculate_outside(int node, int par)
{
    if (par != -1) {
        path_outside[node] = path_outside[par];

        if (topkid[par] != node) {
            path_outside[node] = path_outside[node] + first_inside[par];
        }
        else {
            path_outside[node] = path_outside[node] + second_inside[par];
        }

        path_outside[node].f++;
    }

    // Assume the current node is the one that contains the hardness value

    try_triplet(first_inside[node], second_inside[node], third_inside[node]);
    try_triplet(first_inside[node], second_inside[node], path_outside[node]);
    try_triplet(first_inside[node], third_inside[node], path_outside[node]);
    try_triplet(second_inside[node], third_inside[node], path_outside[node]);

    for (auto neigh : adj_list[node])
        if (neigh != par)
            calculate_outside(neigh, node);
}

int main(void)
{
    scanf("%d", &N);

    adj_list.resize(N);
    first_inside.resize(N);
    second_inside.resize(N);
    third_inside.resize(N);
    path_outside.resize(N);
    total_best.resize(N);
    topkid.assign(N, -1);

    for (int i = 0; i < N - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;

        adj_list[a].pb(b);
        adj_list[b].pb(a);
    }

    calculate_inside(0, -1);
    calculate_outside(0, -1);

    if (ans.f == 0)
        ans.s = (ll)leafs * (leafs - 1) / 2;

    printf("%lld %lld\n", ans.f, ans.s);

    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void try_triplet(pi, pi, pi)':
road.cpp:103:8: warning: unused variable 'chances' [-Wunused-variable]
  103 |     ll chances = (ll)c1 * c2 * c3;
      |        ^~~~~~~
road.cpp: In function 'int main()':
road.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
road.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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