Submission #340360

#	Time	Username	Problem	Language	Result	Execution time	Memory
340360		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, maxi, sol, cnt, ind;
vi e[maxn];
vp dete[maxn];

void dfs(int x, int st, int dist = 1){
    if (maxi<dist){
        maxi=dist;
        ind=x;
    }

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

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

pi g(int x, int st){
    int len = dete[x].size(), stao = 0;

    pi p = {-1, -1}, d = {-1, -1};
    for (int i = 0; i < len; ++i){
        pi t = dete[x][i];

        if (t.second == st) continue;

        if (p.first == -1){
            p = dete[x][i];
            continue;
        }

        d = dete[x][i];
        stao = i;
        break;
    }

    int cur = 0;
    for (int i = stao; i < len; ++i){
        pi t = dete[x][i];
        if (t.second == st) continue;
        if (t.first != d.first) break;
        ++cur;
    }

    if (d.first != p.first)
        return {d.first+p.first,cur};
    return {2*d.first, f(cur+1)};
} 

int vis[maxn];

void update(int res, int cc){
    if (res == sol){
        cnt+=cc;
    }
    if(res > sol){
        sol =res;
        cnt = cc;
    }
}

int maksimalni(int x, int st, int tt){
    for (int i = 0; i < dete[x].size(); ++i){
        if (dete[x][i].second == st || dete[x][i].second == tt) continue;
        return dete[x][i].first;
    }

    return 0;
}

void calc(int x, int st, int dist = 1){

    int len = dete[x].size();
    if (len > 2 && !vis[x]){
        vis[x] = 1;
        pi tmp = g(x, st);
        int res = tmp.first, cc = tmp.second;
        res *= dist;

        update(res, cc);

        int dij = 0;
        for (int i = 0; i < len; ++i)
            if (dete[x][i].second == st)
                dij = dete[x][i].first;       

        for (int i = 0; i < len; ++i)
            if (dete[x][i].second != st){
                res = maksimalni(x, st, dete[x][i].second);
                res *= (dij+dete[x][i].first);
                update(res,1);
            }
    }

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

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){
        for (int j : e[i]){
            maxi=0; ind=0;
            dfs(j,i);
            dete[i].push_back({maxi, j});
        }
        sort(dete[i].rbegin(), dete[i].rend());

        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 len = e[x].size();
        if (len>1) continue;
       // cout << sol << ' ' << cnt << '\n';
      //  cout <<"A " << x << endl;
        calc(e[x][0], x);
    }

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

Compilation message (stderr)

road.cpp: In function 'll maksimalni(ll, ll, ll)':
road.cpp:85:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < dete[x].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~~~

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