Submission #171634

#	Time	Username	Problem	Language	Result	Execution time	Memory
171634		mcdx9524	Hard route (IZhO17_road)	C++14	0 / 100	3 ms	504 KiB

road

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5007;

int n;
vector <int> g[N];
int dep[N];
int root = -1;
map <int, int> cnt;
int mx = -1, mx_cnt = 0;

void pre_dfs(int v, int pr) {
    dep[v] = 1;
    for (int u : g[v]) {
        if (u != pr) {
            pre_dfs(u, v);
            dep[v] = max(dep[v], dep[u] + 1);
        }
    }
}

void dfs(int v, int pr, int cur_mx, int cnt_n) {
    if ((int) g[v].size() == 1 && v != root) {
        cnt[cur_mx * cnt_n]++;
        if (cur_mx * cnt_n > mx) {
            mx = cur_mx * cnt_n;
            mx_cnt = 1;
        } else if (cur_mx * cnt_n == mx) {
            mx_cnt++;
        }
        return;
    }
    pair <int, int> fr = {-1, -1};
    pair <int, int> sc = {-1, -1};
    for (int u : g[v]) {
        if (u != pr) {
            if (dep[u] > fr.first) {
                fr = {dep[u], u};
            } else if (dep[u] > sc.first) {
                sc = {dep[u], u};
            }
        }
    }
    for (int u : g[v]) {
        if (u != pr) {
            if (sc.first == -1) {
                dfs(u, v, cur_mx, cnt_n + 1);
            } else {
                if (fr.second == u) {
                    int new_mx = cur_mx;
                    new_mx = max(new_mx, sc.first);
                    dfs(u, v, new_mx, cnt_n + 1);
                } else {
                    int new_mx = cur_mx;
                    new_mx = max(new_mx, fr.first);
                    dfs(u, v, new_mx, cnt_n + 1);
                }
            }
        }
    }
}

void calc(int v) {
    root = v;
    memset(dep, sizeof dep, 0);
    pre_dfs(v, 0);
    dfs(v, 0, 0, 0);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if ((int) g[i].size() == 1) {
            calc(i);
        }
    }
    cout << mx << ' ' << mx_cnt / 2 << '\n';
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void calc(int)':
road.cpp:69:30: warning: 'memset' used with constant zero length parameter; this could be due to transposed parameters [-Wmemset-transposed-args]
     memset(dep, sizeof dep, 0);
                              ^

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