Submission #697136

#	Time	Username	Problem	Language	Result	Execution time	Memory
697136		FedShat	ROI16_sending (ROI16_sending)	C++17	0 / 100	273 ms	28380 KiB

sending

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

#ifdef __APPLE__
#include "debug.h"
#else
#define debug(...) 42
#endif

vector<vector<int>> g;
constexpr int k = 18;
vector<vector<int>> up;
vector<int> tin, tout, depth;
int timer = 0;

void dfs1(int v, int p) {
    tin[v] = timer++;
    if (p != -1) {
        depth[v] = depth[p] + 1;
        up[0][v] = p;
        for (int i = 1; i < k; ++i) {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
    }
    for (auto u : g[v]) {
        if (u != p) {
            dfs1(u, v);
        }
    }
    tout[v] = timer;
}

bool is_anc(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int up_d(int v, int d) {
    for (int i = k - 1; i >= 0; --i) {
        if (d >= (1 << i)) {
            v = up[i][v];
            d -= (1 << i);
        }
    }
    return v;
}

int LCA(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    u = up_d(u, depth[u] - depth[v]);
    for (int i = k - 1; i >= 0; --i) {
        if (up[i][u] != up[i][v]) {
            u = up[i][u];
            v = up[i][v];
        }
    }
    if (u == v) {
        return u;
    }
    return up[0][u];
}

int ans = -1;
int ansi = -1, ansj = -1;

void ckans(int u, int v, int c) {
    if (ans < c) {
        ans = c;
        ansi = u;
        ansj = v;
    }
}

vector<array<int, 3>> paths;
vector<vector<int>> p1, p2; // eblany, vertical
vector<pair<int, int>> mn1, mn2; // depth and path (for vertical)

void ckmn(int v, pair<int, int> x) {
    if (x.first <= mn1[v].first) {
        mn2[v] = mn1[v];
        mn1[v] = x;
    } else if (x.first <= mn2[v].first) {
        mn2[v] = x;
    }
}

multiset<array<int, 3>> dfs2(int v, int p) {
    for (auto i : p2[v]) {
        int j = paths[i][2];
        ckmn(v, {depth[j], i});
    }
    multiset<array<int, 3>> cur;
    auto upd = [&](int i) {
        int b = paths[i][1], lca = paths[i][2];
        {
            auto it = cur.lower_bound(array<int, 3>{lca, tin[b], -1});
            if (it != cur.end() && (*it)[0] == lca && (*it)[1] < tout[b]) {
                ckans(i, (*it)[2], depth[v] + depth[b] - 2 * depth[lca]);
            }
        }
        for (int j = k - 1; j >= 0; --j) {
            int subtr = up[j][b];
            if (depth[subtr] >= depth[lca]) {
                auto it = cur.lower_bound(array<int, 3>{lca, tin[subtr], -1});
                if (it == cur.end() || (*it)[0] != lca || (*it)[1] >= tout[subtr]) {
                    b = up[j][b];
                }
            }
        }
        if (b != lca) {
            b = up[0][b];
            auto it = cur.lower_bound(array<int, 3>{lca, tin[b], -1});
            assert(it != cur.end() && (*it)[0] == lca && (*it)[1] < tout[b]);
            ckans(i, (*it)[2], depth[v] + depth[b] - 2 * depth[lca]);
        }
    };
    for (auto i : p1[v]) {
        upd(i);
        int j = paths[i][1];
        cur.insert({paths[i][2], tin[j], i});
    }
    for (auto u : g[v]) {
        if (u != p) {
            auto x = dfs2(u, v);
            ckmn(v, mn1[u]);
            ckmn(v, mn2[u]);
            if (cur.size() < x.size()) {
                cur.swap(x);
            }
            for (const auto &ci : x) {
                upd(ci[2]);
                cur.insert(ci);
            }
        }
    }
    if (depth[v] > mn2[v].first) {
        assert(mn1[v].second != mn2[v].second);
        ckans(mn1[v].second, mn2[v].second, depth[v] - mn2[v].first);
    }
    return cur;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, q;
    cin >> n >> q;
    g.resize(n);
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        --p;
        // cout << p + 1 << " " << i + 1 << "\n";
        g[i].push_back(p);
        g[p].push_back(i);
    }
    tin.resize(n);
    tout.resize(n);
    depth.resize(n);
    up.resize(k, vector<int>(n));
    dfs1(0, -1);
    paths.resize(q);
    p1.resize(n);
    p2.resize(n);
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        if (depth[u] < depth[v]) {
            swap(u, v);
        }
        if (is_anc(v, u)) {
            p2[u].push_back(i);
            paths[i] = {u, v, LCA(u, v)};
        } else {
            if (tin[v] < tin[u]) {
                swap(u, v);
            }
            paths[i] = {u, v, LCA(u, v)};
            p1[u].push_back(i);
            p2[u].push_back(i);
            p2[v].push_back(i);
        }
    }
    mn1.resize(n, {INF, -1});
    mn2.resize(n, {INF, -1});
    dfs2(0, -1);
    if (ans == -1) {
        cout << "0\n1 2\n";
    } else {
        cout << ans << "\n";
        // cout << paths[ansi][0] + 1 << " " << paths[ansi][1] + 1 << "\n";
        // cout << paths[ansj][0] + 1 << " " << paths[ansj][1] + 1 << "\n";
        cout << ansi + 1 << " " << ansj + 1 << "\n";
    }
}

• Subtask 1: 0 / 29
• Subtask 2: 0 / 12
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 10