oj.uz

답안 #697111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697111 2023-02-08T12:14:21 Z FedShat 서류 전달 (ROI16_sending) C++17
0 / 100
 299 ms 28392 KB 
#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;
}

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<pair<int, int>> dfs2(int v, int p) {
    for (auto i : p2[v]) {
        int j = paths[i][2];
        if (depth[j] <= depth[v]) {
            ckmn(v, {depth[j], i});
        }
    }
    multiset<pair<int, int>> cur;
    for (auto i : p1[v]) {
        int j = paths[i][1];
        cur.insert({tin[j], i});
    }
    for (auto u : g[v]) {
        if (u != p) {
            auto x = dfs2(u, v);
            if (mn1[u].first <= depth[v]) {
                ckmn(v, mn1[u]);
            }
            if (mn2[u].first <= depth[v]) {
                ckmn(v, mn2[u]);
            }
            if (x.size() < cur.size()) {
                cur.swap(x);
            }
            for (auto [_, i] : x) {
                auto [a, b, lca] = paths[i];
                {
                    auto it = cur.lower_bound({tin[b], -1});
                    if (it != cur.end() && it->first <= tout[b]) {
                        ckans(i, it->second, 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({tin[subtr], -1});
                        if (it == cur.end() || it->first > tout[subtr]) {
                            b = up[j][b];
                        }
                    }
                }
                if (b != lca) {
                    b = up[0][b];
                    auto it = cur.lower_bound({tin[b], -1});
                    assert(it != cur.end() && it->first <= tout[b]);
                    ckans(i, it->second, depth[v] + depth[b] - 2 * depth[lca]);
                }
                cur.insert({b, i});
            }
        }
    }
    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;
        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);
        }
        paths[i] = {u, v, LCA(u, v)};
        p2[u].push_back(i);
        if (!is_anc(v, u)) {
            p1[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 << ansi + 1 << " " << ansj + 1 << "\n";
    }
}

Subtask #1
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 212 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 212 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 212 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 212 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Failed 299 ms 28392 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Failed 137 ms 23268 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 212 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 212 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -