Submission #340319

#	Time	Username	Problem	Language	Result	Execution time	Memory
340319		Sprdalo	Hard route (IZhO17_road)	C++17	19 / 100	16 ms	2284 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 = 105;
int n;
vi e[maxn];
int d[maxn][maxn];
vi put[maxn][maxn];
stack<int> s;

void add(int a, int b){
    auto t = s;

    while(!t.empty()){
        put[a][b].push_back(t.top());
        t.pop();
    }
}

void dfs(int x, int st, int p, int dist = 0){

    s.push(x);
    int lenp = e[p].size(), len = e[x].size();
    if (p != x && len == 1 && lenp == 1){
        add(x, p);
    }

    for (int i : e[x]){
        if (i == st) continue;

        d[i][p] = d[p][i] = dist+1;
        dfs(i,x,p,dist+1);
    }
    s.pop();
}

vi cnt(maxn*maxn, 0), leaf;

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);
    }

    for (int i = 1; i <= n; ++i){
        dfs(i, i, i);
    }

    for (int i = 1; i <= n; ++i){
        int l = e[i].size();
        if (l == 1)
            leaf.push_back(i);
    }

    int len = leaf.size();
    if (len == 2)
        return cout << "0 1\n", 0;

    int maxi = 0;
    for (int x : leaf){
        for (int y : leaf){
            int sol = 0;

            if (x == y) continue;
            for (int z : leaf){
                if (x == y || y == z || x == z) continue;
                int res = d[x][z];
                for (int t : put[x][y])
                    res = min(res, d[t][z]);
                sol = max(sol, res);
            }

            ++cnt[sol*d[x][y]];
            maxi = max(maxi, sol*d[x][y]);
        }
    }

    for (int x : leaf){
        for (int y : leaf){
            int sol = 0;

            if (x == y) continue;
            for (int z : leaf){
                if (x == y || y == z || x == z) continue;
                int res = d[x][z];
                for (int t : put[x][y])
                    res = min(res, d[t][z]);
                sol = max(sol, res);
            }

            if (sol == maxi && d[x][y] != 2) throw SIGSEGV;
        }
    }

    cout << maxi << ' ' << cnt[maxi]/2 << '\n';
}

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