Submission #1233757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233757		Bahamin	Hard route (IZhO17_road)	C++20	52 / 100	508 ms	222664 KiB

road

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 5e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

vector<int> adj[MAX_N];
pair<int, int> ma[MAX_N];
pair<int, int> up[MAX_N];
int dp[MAX_N];
int h[MAX_N];
ll ans1;
ll ans;

void dfs1(int u, int p)
{
    ma[u] = make_pair(0, 1);
    for (int v : adj[u]) if (v != p)
    {   
        h[v] = h[u] + 1;
        dfs1(v, u);
        if (ma[v].first + 1 > ma[u].first) ma[u] = make_pair(ma[v].first + 1, ma[v].second);
        else if (ma[v].first + 1 == ma[u].first) ma[u].second += ma[v].second;
    }
}

void dfs2(int u, int p)
{
    vector<pair<int, int>> vs;
    vs.push_back(make_pair(up[u].first - 1, up[u].second));
    for (int v : adj[u]) if (v != p) vs.push_back(ma[v]);
    sort(all(vs), greater<pair<int, int>>());
    if (adj[u].size() >= 3) 
    {
        ll now = 1ll * (vs[0].first + 1) * (vs[1].first + vs[2].first + 2);
        // cout << u << " " << now << " " << vs << endl;
        int cnt = 0;
        int sum1 = 0;
        for (auto x : vs)
        {
            if (x.first == vs[2].first) cnt += 1ll * sum1 * x.second;
            if (x.first == vs[1].first) sum1 += x.second;
        }
        if (now > ans1) ans = cnt, ans1 = now;
        else if (now == ans1) ans += cnt;
    }
    multiset<int> al;
    map<int, int> sum;
    for (int v : adj[u]) if (v != p) al.insert(ma[v].first), sum[ma[v].first] += ma[v].second;
    for (int v : adj[u]) if (v != p)
    {
        al.erase(al.find(ma[v].first));
        sum[ma[v].first] -= ma[v].second;
        if (al.empty()) up[v] = make_pair(up[u].first + 1, up[u].second);
        else 
        {
            if (up[u].first + 1 > (*al.rbegin()) + 2) up[v] = make_pair(up[u].first + 1, up[u].second);
            else if ((*al.rbegin()) + 2 > up[u].first + 1) up[v] = make_pair((*al.rbegin()) + 2, sum[*al.rbegin()]);
            else up[v] = make_pair(up[u].first + 1, sum[*al.begin()] + up[u].second);
        }
        dfs2(v, u);
        al.insert(ma[v].first);
        sum[ma[v].first] += ma[v].second;
    }
    // cout << u << " " << ma[u] << " " << up[u] << endl;
}

void solve() {
    int n;
    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);
    }
    if (n == 2)
    {
        cout << "0 1" << "\n";
        return;
    }
    int st = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++) 
    {
        if (adj[i].size() > 1) st = i;
        else cnt++;
    }
    up[st].second = 1;
    dfs1(st, 0);
    dfs2(st, 0);
    cout << ans1 << " " << max(1ll, ans) << "\n";
}   

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 0 / 48