oj.uz

Submission #340423

# Submission time Handle Problem Language Result Execution time Memory
340423 2020-12-27T15:08:02 Z Sprdalo Hard route (IZhO17_road) C++17
0 / 100
 1 ms 492 KB 
#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 = 5005;
vi e[maxn], d(maxn);

void dfs(int x, int st){
    d[x] = 0;
    for (int i : e[x]){
        if (i != st)
            d[x] = max(d[x], d[i]);
    }
    ++d[x];
}

int sol, cnt;
void calc(int x, int st, int dij=0, int ds=0){
    int len = e[x].size();
    if (len == 1){
        int res =ds*dij;

        if (sol==res)
            ++cnt;

        if (sol < res){
            sol =res;
            cnt=1;
        }
    }

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

        if (d[i] >= m){
            swap(m,y);
            m=d[i];
        } else if (d[i] >=y){
            y=d[i];
        }
    }

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

        if (m == d[i])
            calc(i,x,dij+1,max(ds,y));
        else
            calc(i,x,dij+1,max(ds,m));
    }
}

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

    int n;
    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 tt = 0;
    for (int i = 1; i <= n; ++i){
        int len = e[i].size();
        tt += (len == 1);
    }

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

    for (int i = 1; i <= n; ++i){
        int len = e[i].size();

        if (len > 1) continue;

        dfs(i,i);
        calc(i,i);
    }

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

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -