Submission #170282

#	Time	Username	Problem	Language	Result	Execution time	Memory
170282		theboatman	Hard route (IZhO17_road)	C++17	0 / 100	2 ms	376 KiB

road

#include <bits/stdc++.h>

#define fi first
#define se second

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;
typedef long long ll;

const long long INF = ll(1e18) + 10;
const int inf = int(1e9) + 10;
const int N = int(1e6) + 10;


pair <ll, int> ans;
vector <pair <int, int> > dp;
vector <vector <int> > g;

//int cnt[N];
void dfs(int v, int from, int deep) {
    pair <int, int> mx = {0, v};

    vector <int> way;
    unordered_map <int, int> cnt;
    for(auto to : g[v]) {
        if (to != from) {
            dfs(to, v, deep + 1);
            mx = max(mx, dp[to]);

            way.push_back(dp[to].fi);
            cnt[dp[to].fi]++;
        }
    }

    sort(way.begin(), way.end());
    way.erase(unique(way.begin(), way.end()), way.end());

    reverse(way.begin(), way.end());

    vector <int> res = way;
    while(res.size() > 2) {
        res.pop_back();
    }

    if (res.size() > 0 && cnt[res[0]] > 1) {
        ll col = cnt[res[0]] * (cnt[res[0]] - 1) / 2;
        ll cur = res[0] * 2 * deep;

        //cout << cur << " " << v + 1 << ": \n";

        ans.fi = max(ans.fi, cur);
    }
    else {
        if (res.size() > 1) {
            ll col = cnt[res[1]];
            ll cur = (res[0] + res[1]) * deep;

            ans.fi = max(ans.fi, cur);
        }
    }

    dp[v] = {mx.fi + 1, mx.se};
}

set <pair <int, int> > kek;
void dfs1(int v, int from, int deep) {
    pair <int, int> mx = {0, v};

    vector <int> way;
    unordered_map <int, vector <int> > cnt;
    for(auto to : g[v]) {
        if (to != from) {
            dfs1(to, v, deep + 1);

            mx = max(mx, dp[to]);
            cnt[dp[to].fi].push_back(dp[to].se);
            way.push_back(dp[to].fi);
        }
    }

    mx.fi++;
    dp[v] = mx;

    sort(way.begin(), way.end());
    way.erase(unique(way.begin(), way.end()), way.end());

    reverse(way.begin(), way.end());

    vector <int> res = way;
    while(res.size() > 2) {
        res.pop_back();
    }

    if (res.size() > 0 && cnt[res[0]].size() > 1) {
        ll cur = res[0] * 2 * deep;

        if (cur != ans.fi) {
            return;
        }

        vector <int> c = cnt[res[0]];
        for(int it = 0; it < c.size(); it++) {
            for(int it1 = it + 1; it1 < c.size(); it1++) {
                int a = c[it];
                int b = c[it1];

                if (a > b) {
                    swap(a, b);
                }

                if (a != b) {
                    kek.insert({a, b});
                }
            }
        }
    }
    else {
        if (res.size() > 1) {
            ll cur = (res[0] + res[1]) * deep;

            if (cur != ans.fi) {
                return;
            }

            for(auto to : cnt[res[1]]) {
                int a = cnt[res[0]][0];
                int b = to;

                if (a > b) {
                    swap(a, b);
                }

                if (a != b) {
                    kek.insert({a, b});
                }

            }
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;

    g.resize(n);
    for(int i = 0; i < n - 1; i++) {
        int v, to;
        cin >> v >> to;
        v--, to--;

        g[v].push_back(to);
        g[to].push_back(v);
    }


    for(int root = 0; root < n; root++) {
        dp.assign(n, {0, 0});

        dfs(root, -1, 0);

    }

    for(int root = 0; root < n; root++) {
        dp.assign(n, {0, 0});

        dfs1(root, -1, 0);
    }

    cout << ans.fi << " " << kek.size() << "\n";
    return 0;
}
/*
*/

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int, int)':
road.cpp:48:12: warning: unused variable 'col' [-Wunused-variable]
         ll col = cnt[res[0]] * (cnt[res[0]] - 1) / 2;
            ^~~
road.cpp:57:16: warning: unused variable 'col' [-Wunused-variable]
             ll col = cnt[res[1]];
                ^~~
road.cpp: In function 'void dfs1(int, int, int)':
road.cpp:104:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int it = 0; it < c.size(); it++) {
                         ~~~^~~~~~~~~~
road.cpp:105:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int it1 = it + 1; it1 < c.size(); it1++) {
                                   ~~~~^~~~~~~~~~

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