Submission #145061

#	Time	Username	Problem	Language	Result	Execution time	Memory
145061		MladenP	Hard route (IZhO17_road)	C++17	100 / 100	1121 ms	62456 KiB

road

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 500010
int N, A, B, X, Y, dist1[MAXN], dist2[MAXN], len[MAXN], cnt[MAXN], L[MAXN];
lld C[MAXN];
vector<int> adj[MAXN];
void dfsMerge(int node, int prev) {
    lld maxi1 = 0, maxi2 = 0;
    for(auto x : adj[node]) {
        if(x != prev) {
            dfsMerge(x, node);
            if(len[x]+1 >= maxi1) maxi2 = maxi1, maxi1 = len[x]+1;
            else if(len[x]+1 >= maxi2) maxi2 = len[x]+1;
        }
    }
    if(maxi2 == 0) return;
    L[node] = maxi1+maxi2;
    if(maxi1 == maxi2) {
        lld sum = 0;
        for(auto x : adj[node]) {
            if(x != prev) {
                if(len[x]+1 == maxi1) C[node] -= cnt[x]*cnt[x], sum += cnt[x];
            }
        }
        C[node] += sum*sum;
        C[node] /= 2;
    } else {
        lld cnt1 = 0, cnt2 = 0;
        for(auto x : adj[node]) {
            if(x != prev) {
                if(len[x]+1 == maxi1) cnt1 += cnt[x];
                if(len[x]+1 == maxi2) cnt2 += cnt[x];
            }
        }
        C[node] = cnt1*cnt2;
    }
}
void dfsDist(int node, int prev, int dist[]) {
    dist[node] = dist[prev]+1;
    for(auto x : adj[node]) {
       if(x != prev) dfsDist(x, node, dist);
    }
}
pii dfsMaxPut(int node, int prev) {
    cnt[node] = 1;
    for(auto x : adj[node]) {
        if(x != prev) {
            pii cur = dfsMaxPut(x, node);
            if(cur.fi+1 > len[node]) {
                len[node] = cur.fi+1;
                cnt[node] = cur.se;
            } else if(cur.fi+1 == len[node]) cnt[node] += cur.se;
        }
    }
    return {len[node], cnt[node]};
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> N;
    for(int i = 1; i < N; i++) {
        int x, y; cin >> x >> y;
        adj[x].pb(y); adj[y].pb(x);
    }
    dist1[1] = -1; dfsDist(1, 1, dist1);
    for(int i = 1; i <= N; i++) if(dist1[i] > dist1[A]) A = i;
    dist1[A] = -1; dfsDist(A, A, dist1);
    for(int i = 1; i <= N; i++) if(dist1[i] > dist1[B]) B = i;
    dist2[B] = -1; dfsDist(B, B, dist2);
    int rast = INF, prec = 0;
    for(int i = 1; i <= N; i++) {
        int eks = max(dist1[i], dist2[i]);
        prec = max(prec, dist1[i]);
        if(eks == rast) Y = i;
        else if(eks < rast) X = i, Y = 0, rast = eks;
    }
    if(prec == N-1) {
        cout << 0 << ' ' << 1 << endl;
        return 0;
    }
    lld score = 0, Cnt = 0;
    if(Y == 0) {
        dfsMaxPut(X, X);
        dfsMerge(X, X);
        for(int i = 1; i <= N; i++) {
            if(i != X) {
                lld cur = (lld)(prec-len[i])*(L[i]);
                if(cur > score) {
                    Cnt = C[i];
                    score = cur;
                } else if(cur == score) Cnt += C[i];
            }
        }
        ///PUTEVI KOJI PROLAZE KROZ CENTAR
        if(adj[X].size() > 2) {
            lld maxi1 = 0, maxi2 = 0, br = 0, cnt1 = 0, cnt2 = 0;
            for(auto x : adj[X]) {
                if(len[x]+1 > maxi1) maxi2 = maxi1, maxi1 = len[x]+1;
                else if(len[x]+1 > maxi2) maxi2 = len[x]+1;
            }
            for(auto x : adj[X]) {
                if(len[x]+1 == maxi1) br++, cnt1 += cnt[x];
                if(len[x]+1 == maxi2) cnt2 += cnt[x];
            }
            if(br <= 2) {
                if(maxi1*(maxi1+maxi2) > score) score = maxi1*(maxi1+maxi2), Cnt = cnt1*cnt2;
                else if(maxi1*(maxi1+maxi2) == score) Cnt += cnt1*cnt2;
            } else {
                lld curS = cnt1*cnt1;
                for(auto x : adj[X]) {
                    if(len[x]+1 == maxi1) curS -= cnt[x]*cnt[x];
                }
                curS /= 2;
                if(2*maxi1*maxi1 > score) score = 2*maxi1*maxi1, Cnt = curS;
                else if(2*maxi1*maxi1 == score) Cnt += curS;
            }
        }
        ///
    } else {
        dfsMaxPut(X, Y); dfsMaxPut(Y, X);
        dfsMerge(X, Y); dfsMerge(Y, X);
        for(int i = 1; i <= N; i++) {
            lld cur = (lld)(prec-len[i])*(L[i]);
            if(cur > score) {
                Cnt = C[i];
                score = cur;
            } else if(cur == score) Cnt += C[i];
        }
    }
    cout << score << ' ' << Cnt << endl;
    return 0;
}

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