oj.uz

Submission #340319

# Submission time Handle Problem Language Result Execution time Memory
340319 2020-12-27T12:28:01 Z Sprdalo Hard route (IZhO17_road) C++17
19 / 100
 16 ms 2284 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;
    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.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 Correct 2 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 14 ms 1388 KB Output is correct
12 Correct 11 ms 1388 KB Output is correct
13 Correct 11 ms 1388 KB Output is correct
14 Correct 11 ms 1388 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 748 KB Output is correct
19 Correct 1 ms 748 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 1 ms 748 KB Output is correct
22 Correct 1 ms 748 KB Output is correct
23 Correct 1 ms 748 KB Output is correct
24 Correct 16 ms 1260 KB Output is correct

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 Correct 2 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 14 ms 1388 KB Output is correct
12 Correct 11 ms 1388 KB Output is correct
13 Correct 11 ms 1388 KB Output is correct
14 Correct 11 ms 1388 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 748 KB Output is correct
19 Correct 1 ms 748 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 1 ms 748 KB Output is correct
22 Correct 1 ms 748 KB Output is correct
23 Correct 1 ms 748 KB Output is correct
24 Correct 16 ms 1260 KB Output is correct
25 Runtime error 4 ms 2284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 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 Correct 2 ms 876 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 14 ms 1388 KB Output is correct
12 Correct 11 ms 1388 KB Output is correct
13 Correct 11 ms 1388 KB Output is correct
14 Correct 11 ms 1388 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 748 KB Output is correct
19 Correct 1 ms 748 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 1 ms 748 KB Output is correct
22 Correct 1 ms 748 KB Output is correct
23 Correct 1 ms 748 KB Output is correct
24 Correct 16 ms 1260 KB Output is correct
25 Runtime error 4 ms 2284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -