Submission #898498

#	Time	Username	Problem	Language	Result	Execution time	Memory
898498		Alcabel	Torrent (COI16_torrent)	C++17	0 / 100	163 ms	59828 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5, inf = 1e9;
vector<int> g[maxn];

vector<int> getPath(int v, int p, int t) {
    if (v == t) {
        return {v};
    }
    vector<int> res;
    for (const int& u : g[v]) {
        if (u != p) {
            res = getPath(u, v, t);
            if (!res.empty()) {
                res.emplace_back(v);
                return res;
            }
        }
    }
    return {};
}

char isOnPath[maxn];
int dp[maxn];
vector<int> prefMax[maxn], sufMax[maxn];

void dfsDp(int v, int p) {
    dp[v] = 0;
    for (int i = 0; i < (int)g[v].size(); ++i) {
        int u = g[v][i];
        if (u != p && !isOnPath[u]) {
            dfsDp(u, v);
        } else {
            swap(g[v][i], g[v].back());
            g[v].pop_back();
            --i;
        }
    }
    sort(g[v].begin(), g[v].end(), [&](const int& A, const int& B) {
        return dp[A] < dp[B];
    });
    dp[v] = 0;
    prefMax[v].resize(g[v].size() + 1);
    prefMax[v][0] = -1;
    for (int i = 0; i < (int)g[v].size(); ++i) {
        int cur = dp[g[v][i]] + (int)g[v].size() - i;
        prefMax[v][i + 1] = max(prefMax[v][i], cur);
        dp[v] = max(dp[v], cur);
    }
    sufMax[v].resize(g[v].size() + 1);
    sufMax[v].back() = -1;
    for (int i = (int)g[v].size() - 1; i >= 0; --i) {
        int cur = dp[g[v][i]] + (int)g[v].size() - i;
        sufMax[v][i] = max(sufMax[v][i + 1], cur);
    }
}

void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    --a, --b;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].emplace_back(u);
        g[u].emplace_back(v);
    }
    vector<int> path = getPath(a, -1, b);
    for (const int& v : path) {
        isOnPath[v] = true;
    }
    for (const int& v : path) {
        dfsDp(v, -1);
    }
    int k = path.size();
    vector<long long> maxR(k), maxL(k);
    int left = -1, right = n - 2;
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        maxR[0] = mid;
        bool able = true;
        for (int i = 0; i < k - 2; ++i) {
            int v = path[i];
            bool defined = false;
            for (int j = g[v].size(); j >= 0; --j) {
                // max(prefMax[v][j] + 1, sufMax[v][j], x + g[v].size() + 1 - j) <= maxR[i]
                // x >= (j > 0 ? dp[g[v][j - 1]] : -inf)
                long long maxx = maxR[i] - ((int)g[v].size() + 1 - j);
                if (j < (int)g[v].size()) {
                    maxx = min(maxx, dp[g[v][j]] * 1ll);
                }
                long long minx = (j > 0 ? dp[g[v][j - 1]] : -inf);
                if (max(prefMax[v][j] + 1, sufMax[v][j]) <= maxR[i] && minx <= maxx) {
                    maxR[i + 1] = maxx;
                    defined = true;
                    break;
                }
            }
            if (!defined) {
                able = false;
                break;
            }
        }
        maxL[k - 1] = mid;
        for (int i = k - 1; i > 1; --i) {
            int v = path[i];
            bool defined = false;
            for (int j = g[v].size(); j >= 0; --j) {
                // max(prefMax[v][j] + 1, sufMax[v][j], x + g[v].size() + 1 - j) <= maxL[i]
                // x >= (j > 0 ? dp[g[v][j - 1]] : -inf)
                long long maxx = maxL[i] - ((int)g[v].size() + 1 - j);
                if (j < (int)g[v].size()) {
                    maxx = min(maxx, dp[g[v][j]] * 1ll);
                }
                long long minx = (j > 0 ? dp[g[v][j - 1]] : -inf);
                if (max(prefMax[v][j] + 1, sufMax[v][j]) <= maxL[i] && minx <= maxx) {
                    maxL[i - 1] = maxx;
                    defined = true;
                    break;
                }
            }
            if (!defined) {
                able = false;
                break;
            }
        }
        if (able) {
            able = false;
            for (int i = 0; i < k - 1; ++i) {
                if (maxR[i] >= dp[path[i]] && maxL[i + 1] >= dp[path[i + 1]]) {
                    able = true;
                    break;
                }
            }
        }
        if (able) {
            right = mid;
        } else {
            left = mid;
        }
    }
    cout << right << '\n';
}

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

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69