Submission #340321

#	Time	Username	Problem	Language	Result	Execution time	Memory
340321		Sprdalo	Hard route (IZhO17_road)	C++17	0 / 100	1 ms	492 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, maxi, sol, cnt;
vi e[maxn], d(maxn);

void dfs(int x, int st, int dist = 0){
    maxi = max(maxi, dist);

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

int f(int x){
    int s = x * (x-1);
    return s/2;
}

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

    cin >> n;

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

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

    int t = 0;
    for (int i = 1; i <= n; ++i){
        maxi = 0;
        dfs(i,i);
        d[i]=maxi;

        int len = e[i].size();
        t += (len == 1);
    }

    if (t == 2)
        return cout << "0 1\n", 0;

    for (int x = 1; x <= n; ++x){
        int cur = 0;
        for (int i : e[x]){
            int len = e[i].size();
            cur += (len == 1);
        }

        if (cur<2) continue;

        int res = d[x] * 2;
        if (sol == res){
            cnt += f(cur);
        }

        if (sol < res){
            sol = res;
            cnt = f(cur);
        }
    }

    cout << sol << ' ' << cnt << '\n';
}

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