oj.uz

Submission #758168

# Submission time Handle Problem Language Result Execution time Memory
758168 2023-06-14T08:32:35 Z vjudge1 Hard route (IZhO17_road) C++17
0 / 100
 9 ms 12116 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mxN = 5e5 + 7;

int mx, d[mxN], ans, cnt, og;
vector<int> g[mxN], a, b;
set<pair<int,int>> check;

void findFirst(int u, int par, int dist) {
    if (dist > mx) {
        mx = dist;
        a.clear();
        a.push_back(u);
    }
    else {
        a.push_back(u);
    }

    for (auto v : g[u]) {
        if (v != par) {
            findFirst(v, u, dist + 1);
        }
    }
}

void findSecond(int u, int par, int dist) {
    d[u] = dist;
    if (dist > mx) {
        mx = dist;
        b.clear();
        b.push_back(u);
    }
    else if (dist == mx) {
        b.push_back(u);
    }

    for (auto v : g[u]) {
        if (v != par) {
            findSecond(v, u, dist + 1);
        }
    }
}
    
void dfs(int u, int par, int dist, int cur) {
    cur = min(cur, d[u]);
    if (g[u].size() == 1 && par) {
        if (dist * cur > ans) {
            ans = dist * cur;
            check.clear();
            check.insert({og, u});
            check.insert({u, og});
        }
        else if (dist * cur == ans) {
            ++cnt;
            check.insert({og, u});
            check.insert({u, og});
        }
    }

    for (auto v : g[u]) {
        if (v != par) {
            dfs(v, u, dist + 1, cur);
        } 
    }
}

int32_t main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    mx = -1;
    findFirst(1, 0, 0);
    a.push_back(1);
    
    ans = -1;
    for (auto u : a) {
        mx = -1;
        findSecond(u, 0, 0);

        for (auto v : b) {
            og = v;
            dfs(v, 0, 0, d[v]);
        }
        b.clear();
    }
    cout << ans << ' ' << check.size() / 2 << "\n";
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 12060 KB Output is correct
11 Incorrect 7 ms 11988 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 12060 KB Output is correct
11 Incorrect 7 ms 11988 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 9 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 7 ms 12060 KB Output is correct
11 Incorrect 7 ms 11988 KB Output isn't correct
12 Halted 0 ms 0 KB -