Submission #170306

#	Time	Username	Problem	Language	Result	Execution time	Memory
170306		nvmdava	Hard route (IZhO17_road)	C++17	100 / 100	1036 ms	64888 KiB

road

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 500005

int dep[N], par[N];
bool bl[N];
vector<int> adj[N];

int dfs1(int v, int p){
    par[v] = p;
    dep[v] = dep[p] + 1;
    int res = v;
    for(int& x : adj[v]){
        if(p == x) continue;
        int w = dfs1(x, v);
        if(dep[w] > dep[res])
            res = w;
    }
    return res;
}

ll ans = 0, cnt = 1;

int d[N];
int dia;

bool ok[N];

pair<int, int> dfs3(int v, int p){
    d[v] = d[p] + 1;
    pair<int, int> res = {d[v], 1};
    if(p != 0){
        for(int& x : adj[v]){
            if(x == p) continue;
            pair<int, int> tmp = dfs3(x, v);
            if(res.ff < tmp.ff){
                res = tmp;
            } else if(res.ff == tmp.ff){
                res.ss += tmp.ss;
            }
        }
        return res;
    }
    int t = 0;
    ll cntr = 0, s = 0;
    for(int& x : adj[v]){
        pair<int, int> tmp = dfs3(x, v);
        if(tmp.ff == dia / 2) ++t;
        cntr += s * tmp.ss;
        s += tmp.ss;
    }
    if(t > 2){
        ans = 1LL * dia * dia / 2;
        cnt = cntr;
    }
    return res;
}

pair<int, int> dfs2(int v, int p){
    d[v] = d[p] + 1;
    pair<int, int> res = {d[v], 1};
    
    int sum = 0;
    ll cntr = 0;

    pair<int, int> b1 = {0, 0};

    for(auto& x : adj[v]){
        if(x == p || bl[x]) continue;
        pair<int, int> tmp = dfs2(x, v);
        if(tmp.ff > res.ff){
            res = tmp;
        } else if(tmp.ff == res.ff){
            res.ss += tmp.ss;
        }


        if(tmp.ff + b1.ff > sum){
            cntr = 1LL * tmp.ss * b1.ss;
            sum = tmp.ff + b1.ff;
            if(tmp.ff > b1.ff){
                b1 = tmp;
            } else if(tmp.ff == b1.ff){
                b1.ss += tmp.ss;
            }
        } else if(tmp.ff + b1.ff == sum){
            cntr += 1LL * tmp.ss * b1.ss;
            if(tmp.ff == b1.ff){
                b1.ss += tmp.ss;
            }
        }
    }

    if(ok[v] && sum != res.ff){
        sum -= 2 * d[v];
        ll a2 = 1LL * sum * max(dia - dep[v], dep[v]);
        if(ans < a2){
            ans = a2;
            cnt = cntr;
        } else if(ans == a2)
            cnt += cntr;
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    int v1 = dfs1(1, 0);
    int v2 = dfs1(v1, 0);
    d[0] = -1;

    dia = dep[v2];
    if(dia % 2 == 0){
        int w = dia / 2;
        int v = v2;
        while(w--)
            v = par[v];
        dfs3(v, 0);
        if(ans){
            cout<<ans<<' '<<cnt<<'\n';
            return 0;
        }
    }
    int qv = par[v2];
    while(qv != v1){
        ok[qv] = 1;
        qv = par[qv];
    }

    if(dia % 2 == 0){
        int w = dia / 2 - 1;
        int u = v2;
        while(w--)
            u = par[u];
        int u2 = par[u];
        int u3 = par[u2];
        bl[u3] = 1;
        dfs2(u2, 0);
        bl[u3] = 0;
        bl[u] = 1;
        dfs2(u2, 0);
        bl[u] = 0;
    } else {
        int w = dia / 2;
        int u = v2;
        while(w--)
            u = par[u];
        int u2 = par[u];
        bl[u2] = 1;
        dfs2(u, 0);
        bl[u2] = 0;
        bl[u] = 1;
        dfs2(u2, 0);
        bl[u] = 0;
    }
    cout<<ans<<' '<<cnt;
}

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