Submission #55566

#	Time	Username	Problem	Language	Result	Execution time	Memory
55566		BThero	Hard route (IZhO17_road)	C++14	19 / 100	2053 ms	12992 KiB

road

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = 5e5+5;

vector<int> adj[MAXN];

pair<int, int> mxP1[MAXN];

vector<pair<int, int>> S; 

int dist[MAXN];

int par[MAXN];

int mxP2[MAXN];

int d[MAXN];

int ans1, ans2;

int n;

void dfs(int v, int pr) {
    mxP1[v] = mp(0, -1);
    mxP2[v] = d[v] = 0;

    for (int to : adj[v]) {
        if (to == pr) {
            continue;
        }

        dfs(to, v);

        if (mxP1[to].fi + 1 > mxP1[v].fi) {
            mxP2[v] = mxP1[v].fi;
            mxP1[v] = mp(mxP1[to].fi + 1, to);
        } 
        else if (mxP1[to].fi + 1 > mxP2[v]) {
            mxP2[v] = mxP1[to].fi + 1;
        }
    }
}

void dfs2(int v, int pr) {
    for (int to : adj[v]) {
        if (to == pr) {
            continue;
        }

        d[to] = max(d[to], d[v] + 1);

        if (mxP1[v].se == to) {
            d[to] = max(d[to], mxP2[v] + 1);
        }
        else {
            d[to] = max(d[to], mxP1[v].fi + 1);
        }

        dfs2(to, v);
    }
}

void goLeaf(int v, int pr) {
    if (adj[v].size() == 1) {
        S.pb(mp(v, 0));
    }

    for (int to : adj[v]) {
        if (to == pr) {
            continue;
        }

        goLeaf(to, v);
    }
}

void getPath(int v, int pr, int en) {
    if (v == en) {
        return;
    }

    for (int to : adj[v]) {
        if (to == pr) {
            continue;
        }

        par[to] = v;
        getPath(to, v, en);
    }
}

int getMx(vector<int> vv) {
    static queue<int> q;

    for (int i = 1; i <= n; ++i) {
        d[i] = n + 1;
    }

    for (int x : vv) {
        d[x] = 0;
        q.push(x);
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : adj[v]) {
            if (d[to] == n + 1) {
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }

    return *max_element(d + 1, d + n + 1);
}      

void solve() {
    scanf("%d", &n);

    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1, -1);
    dfs2(1, -1);

    for (int i = 1; i <= n; ++i) {
        d[i] = max(d[i], mxP1[i].fi);
    }
                  
    goLeaf(1, -1);
    vector<int> vv;

    for (int i = 0; i < S.size(); ++i) {
        for (int j = i + 1; j < S.size(); ++j) {
            par[S[i].fi] = 0;            
            getPath(S[i].fi, -1, S[j].fi);
            vv.clear();

            for (int x = S[j].fi; x; x = par[x]) {
                vv.pb(x);
            }

            int dist = vv.size() - 1;
            int mx = getMx(vv);

            int cur = mx * dist;

            if (cur > ans1) {
                ans1 = cur;
                ans2 = 0;
            }

            if (cur == ans1) {
                ++ans2;
            }
        }
    }

    printf("%d %d\n", ans1, ans2);
}

int main() {            
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:152:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < S.size(); ++i) {
                     ~~^~~~~~~~~~
road.cpp:153:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i + 1; j < S.size(); ++j) {
                             ~~^~~~~~~~~~
road.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
road.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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