Submission #340293

#	Time	Username	Problem	Language	Result	Execution time	Memory
340293		Sprdalo	Hard route (IZhO17_road)	C++17	0 / 100	1 ms	620 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 = 5010;
int n, sol = 0;
vi e[maxn];
vp dete[maxn];

int maxd = 0;
void calc(int x, int st, int dist = 1){
    maxd = max(maxd, dist);

    for (int i : e[x]){
        if (i == st) continue;
        calc(i, x, dist+1);
    }
}

int cnt[maxn][maxn];

void dfs(int x, int st, int d = 0){
    int len = dete[x].size();

    if (len > 2){
        pi prvi = {-1, -1}, drugi = {-1, -1};
        for (int i = 0; i < 3; ++i){
            if (dete[x][i].second == st) continue;
            if (prvi.first == -1)
                prvi = dete[x][i];
            else
                drugi = dete[x][i];
        }

        int res = prvi.first + drugi.first; res *= d;
        if (res > sol){
            sol = res;
            cnt[prvi.second][drugi.second] = res;
            cnt[drugi.second][prvi.second] = res;
        } else if (res == sol){
            cnt[prvi.second][drugi.second] = res;
            cnt[drugi.second][prvi.second] = res;
        }
    }

    for (int i : e[x]){
        if (i == st) continue;
        dfs(i, x, d+1);
    }
}

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

    cin >> n;
    if (n > 5000) throw SIGSEGV;

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

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

    int k = 0;
    for (int i = 1; i <= n; ++i){
        int len = e[i].size();
        k += (len==1);
    }
    if (k == 2) return cout << "0 1\n", 0;

    for (int i = 1; i <= n; ++i){
        for (int x : e[i]){
            maxd = 0;
            calc(x, i);
            dete[i].push_back({maxd, x});
        }
        sort(dete[i].rbegin(), dete[i].rend());
    }

    for (int x = 1; x <= n; ++x){

        dfs(x, x);
    }

    int res = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (cnt[i][j] == sol)
                ++res;

    cout << sol << ' ' << res/2 << '\n';
}

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