oj.uz

Submission #947052

# Submission time Handle Problem Language Result Execution time Memory
947052 2024-03-15T12:47:31 Z atom Hard route (IZhO17_road) C++17
19 / 100
 2000 ms 12376 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 5e5 + 5;
int n;
vector <int> adj[N];
vector <int> path;
bool found;

void dfs(int a, int b, int p) {
    if (found) return;
    path.push_back(a);
    for (int v : adj[a]) {
        if (v == p) continue;
        dfs(v, b, a);
        if (v == b) {
            path.push_back(b);
            found = true;
            return;
        }
    }
    if (found) return;
    path.pop_back();
}
signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //sub1: O(n^3)
    vector <int> ter;
    for (int i = 1; i <= n; ++i)
        if ((int) adj[i].size() == 1)
            ter.push_back(i);

    int ans = 0, cnt = 0;
    for (int i = 0; i < (int) ter.size(); ++i) {
        for (int j = i + 1; j < (int) ter.size(); ++j) {
            path.clear(); found = false;
            dfs(ter[i], ter[j], 0);

            vector <int> dis(n + 5, 1e9);
            queue <int> q;
            for (int x : path) {
                q.push(x);
                dis[x] = 0;
            }

            while (!q.empty()) {
                int x = q.front(); q.pop();
                for (int y : adj[x]) {
                    if (dis[y] > dis[x] + 1) {
                        dis[y] = dis[x] + 1;
                        q.push(y);
                    }
                }
            }

            int len = (int) path.size() - 1;
            int h = 0;
            for (int x = 1; x <= n; ++x)
                h = max(h, dis[x]);
            if (h == (int) (1e9)) h = 0;
            
            if (ans < h * len) {
                ans = h * len;
                cnt = 1;
            }
            else if (ans == h * len) {
                cnt++;
            }
        }
    }

    cout << ans << " " << cnt << "\n";

    return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 4 ms 12196 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 3 ms 12120 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12124 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 3 ms 12120 KB Output is correct
20 Correct 4 ms 12124 KB Output is correct
21 Correct 3 ms 12124 KB Output is correct
22 Correct 3 ms 12124 KB Output is correct
23 Correct 3 ms 12120 KB Output is correct
24 Correct 10 ms 12376 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 4 ms 12196 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 3 ms 12120 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12124 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 3 ms 12120 KB Output is correct
20 Correct 4 ms 12124 KB Output is correct
21 Correct 3 ms 12124 KB Output is correct
22 Correct 3 ms 12124 KB Output is correct
23 Correct 3 ms 12120 KB Output is correct
24 Correct 10 ms 12376 KB Output is correct
25 Execution timed out 2060 ms 12376 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 4 ms 12196 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 4 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 3 ms 12120 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12124 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 3 ms 12120 KB Output is correct
20 Correct 4 ms 12124 KB Output is correct
21 Correct 3 ms 12124 KB Output is correct
22 Correct 3 ms 12124 KB Output is correct
23 Correct 3 ms 12120 KB Output is correct
24 Correct 10 ms 12376 KB Output is correct
25 Execution timed out 2060 ms 12376 KB Time limit exceeded
26 Halted 0 ms 0 KB -