Submission #91630

#	Time	Username	Problem	Language	Result	Execution time	Memory
91630		popovicirobert	Hard route (IZhO17_road)	C++14	100 / 100	1527 ms	159608 KiB

road

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 5e5;

vector <int> g[MAXN + 1];
pair <int, int> down[MAXN + 1], up[MAXN + 1];

pair <ll, ll> ans = {0, 1};

inline void update(pair <int, int> &a, pair <int, int> b) {
    if(b.second == 0) {
        return ;
    }
    if(a.first < b.first) {
        a = b;
    }
    else if(a.first == b.first) {
        a.second += b.second;
    }
}

inline void update(pair <ll, ll> &a, pair <ll, ll> b) {
    if(b.second == 0) {
        return ;
    }
    if(a.first < b.first) {
        a = b;
    }
    else if(a.first == b.first) {
        a.second += b.second;
    }
}

void dfs_down(int nod, int par) {
    down[nod] = {0, 1};
    for(auto it : g[nod]) {
        if(it != par) {
            dfs_down(it, nod);
            update(down[nod], {down[it].first + 1, down[it].second});
        }
    }
}


void dfs_up(int nod, int par) {
    int sz = g[nod].size();
    vector < pair <int, int> > pref(sz), suff(sz);
    for(int i = 0; i < sz; i++) {
        int it = g[nod][i];
        if(i > 0) {
            pref[i] = pref[i - 1];
        }
        if(it == par) {
            continue;
        }
        update(pref[i], {down[it].first + 2, down[it].second});
    }
    for(int i = sz - 1; i >= 0; i--) {
        int it = g[nod][i];
        if(i < sz - 1) {
            suff[i] = suff[i + 1];
        }
        if(it == par) {
            continue;
        }
        update(suff[i], {down[it].first + 2, down[it].second});
    }
    for(int i = 0; i < sz; i++) {
        int it = g[nod][i];
        if(it != par) {
            update(up[it], {up[nod].first + 1, up[nod].second});
            if(i > 0) {
                update(up[it], pref[i - 1]);
            }
            if(i < sz - 1) {
                update(up[it], suff[i + 1]);
            }
            dfs_up(it, nod);
        }
    }
}

inline bool cmp(pair <int, int> a, pair <int, int> b) {
    return a.first > b.first;
}

struct Data {
    int val, cnt, nr;
};

void solve(int nod, int par) {
    vector < pair <int, int> > arr;
    for(auto it : g[nod]) {
        if(it != par) {
            arr.push_back({down[it].first + 1, down[it].second});
        }
    }
    if(up[nod].first > 0) {
        arr.push_back(up[nod]);
    }
    sort(arr.begin(), arr.end(), cmp);
    while(arr.size() >= 3 && arr.back().first < arr[2].first) {
        arr.pop_back();
    }
    if(arr.size() >= 3) {
        vector < Data > aux;
        int sz = arr.size();
        int i = 0;
        while(i < sz) {
            int j = i;
            int cnt = 0;
            while(j < sz && arr[i].first == arr[j].first) {
                cnt += arr[j].second;
                j++;
            }
            aux.push_back({arr[i].first, cnt, j - i});
            i = j;
        }
        if(aux.size() == 1) {
            vector <ll> dp(3);
            for(auto it : arr) {
                vector <ll> new_dp(3);
                new_dp[1] = dp[1] + it.second;
                new_dp[2] = dp[2] + dp[1] * it.second;
                swap(dp, new_dp);
            }
            update(ans, {2LL * aux[0].val * aux[0].val, dp[2]});
        }
        else if(aux.size() == 2) {
            vector <ll> dp(3);
            if(aux[0].nr > 1) {
                update(ans, {1LL * aux[0].val * (aux[0].val + aux[1].val), 1LL * aux[0].cnt * aux[1].cnt});
            }
            else {
                for(int i = 0; i < arr.size(); i++) {
                    if(arr[i].first == aux[1].val) {
                        vector <ll> new_dp(3);
                        new_dp[1] = dp[1] + arr[i].second;
                        new_dp[2] = dp[2] + dp[1] * arr[i].second;
                        swap(dp, new_dp);
                    }
                }
                update(ans, {2LL * aux[0].val * aux[1].val, dp[2]});
            }
        }
        else {
            update(ans, {1LL * aux[0].val * (aux[1].val + aux[2].val), 1LL * aux[1].cnt * aux[2].cnt});
        }
    }
    for(auto it : g[nod]) {
        if(it != par) {
            solve(it, nod);
        }
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = -1;
    for(i = 1; i <= n; i++) {
        if(g[i].size() > 1) {
            root = i;
            break;
        }
    }
    if(root > -1) {
        dfs_down(root, 0);
        up[root] = {-MAXN, 0};
        dfs_up(root, 0);
        solve(root, 0);
    }
    cout << ans.first << " " << ans.second;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void solve(int, int)':
road.cpp:143:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i = 0; i < arr.size(); i++) {
                                ~~^~~~~~~~~~~~

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