oj.uz

Submission #340323

# Submission time Handle Problem Language Result Execution time Memory
340323 2020-12-27T12:41:01 Z Sprdalo Hard route (IZhO17_road) C++17
0 / 100
 5 ms 1644 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 = 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, mini = n;
    for (int x : leaf){
        for (int y : leaf){
            int sol = 0;

            if (x == y) continue;
            mini = min(mini, d[x][y]);
            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*d[x][y] == maxi && d[x][y] != mini) throw SIGSEGV;
        }
    }

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

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Runtime error 5 ms 1644 KB Execution killed with signal 6 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Runtime error 5 ms 1644 KB Execution killed with signal 6 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Runtime error 5 ms 1644 KB Execution killed with signal 6 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -