Submission #916082

#	Time	Username	Problem	Language	Result	Execution time	Memory
916082		Alcabel	Prize (CEOI22_prize)	C++17	100 / 100	2156 ms	228620 KiB

Main

#pragma GCC optimize("O3", "Ofast")
// #pragma GCC optimize("avx", "avx2")
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6;
vector<int> g1[maxn], g2[maxn];
int h1[maxn], h2[maxn], tin1[maxn], tin2[maxn], tt;
int par1[maxn], par2[maxn], jump1[maxn], jump2[maxn];

vector<int> vset;

void dfs1(int v, int k) {
    if (tin2[v] < k) {
        vset.emplace_back(v);
    }
    tin1[v] = tt++;
    for (const int& u : g1[v]) {
        h1[u] = h1[v] + 1;
        if (h1[jump1[jump1[v]]] - h1[jump1[v]] == h1[jump1[v]] - h1[v]) {
            jump1[u] = jump1[jump1[v]];
        } else {
            jump1[u] = v;
        }
        dfs1(u, k);
    }
}
 
void dfs2(int v) {
    tin2[v] = tt++;
    for (const int& u : g2[v]) {
        h2[u] = h2[v] + 1;
        if (h2[jump2[jump2[v]]] - h2[jump2[v]] == h2[jump2[v]] - h2[v]) {
            jump2[u] = jump2[jump2[v]];
        } else {
            jump2[u] = v;
        }
        dfs2(u);
    }
}

int getLca1(int v, int u) {
    if (h1[v] < h1[u]) { swap(v, u); }
    while (h1[v] != h1[u]) {
        if (h1[jump1[v]] > h1[u]) {
            v = jump1[v];
        } else {
            v = par1[v];
        }
    }
    while (v != u) {
        if (jump1[v] != jump1[u]) {
            v = jump1[v], u = jump1[u];
        } else {
            v = par1[v], u = par1[u];
        }
    }
    return v;
}

int getLca2(int v, int u) {
    if (h2[v] < h2[u]) { swap(v, u); }
    while (h2[v] != h2[u]) {
        if (h2[jump2[v]] > h2[u]) {
            v = jump2[v];
        } else {
            v = par2[v];
        }
    }
    while (v != u) {
        if (jump2[v] != jump2[u]) {
            v = jump2[v], u = jump2[u];
        } else {
            v = par2[v], u = par2[u];
        }
    }
    return v;
}

const int maxq = 1e5;
int newV1[maxn];
vector<pair<int, int>> w1[2 * maxq], w2[maxq];
char vis[2 * maxq];
int dist1[2 * maxq], dist2[maxq];

void dfsCalc1(int v) {
    // cerr << "v: " << v + 1 << ", dist1: " << dist1[v] << '\n';
    vis[v] = tt;
    for (const auto [u, delta] : w1[v]) {
        if (vis[u] < tt) {
            dist1[u] = dist1[v] + delta;
            dfsCalc1(u);
        }
    }
}
 
void dfsCalc2(int v) {
    // cerr << "v: " << v + 1 << ", dist2: " << dist2[v] << '\n';
    vis[v] = tt;
    for (const auto& [u, delta] : w2[v]) {
        if (vis[u] < tt) {
            dist2[u] = dist2[v] + delta;
            dfsCalc2(u);
        }
    }
}
 
void solve() {
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    int root1 = -1, root2 = -1;
    for (int i = 0; i < n; ++i) {
        // newV1[i] = -1;
        cin >> par1[i];
        --par1[i];
        if (par1[i] != -2) {
            g1[par1[i]].emplace_back(i);
        } else {
            par1[i] = i;
            jump1[i] = i;
            root1 = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        cin >> par2[i];
        --par2[i];
        if (par2[i] != -2) {
            g2[par2[i]].emplace_back(i);
        } else {
            par2[i] = i;
            jump2[i] = i;
            root2 = i;
        }
    }
    tt = 0;
    dfs2(root2);
    tt = 0;
    dfs1(root1, k);
    vector<int> comp1(2 * k - 1);
    for (int i = 0; i < k; ++i) {
        cout << vset[i] + 1 << ' ';
        comp1[i] = vset[i];
    }
    cout << endl;
    /*for (int i = 0; i < n; ++i) {
        dsu.minH[i] = {tin1[i], i};
    }*/
    vector<int> lca1(k - 1), lca2(k - 1);
    int comproot1 = -1, comproot2 = -1;
    for (int i = 0; i < k - 1; ++i) {
        int v = vset[i], u = vset[i + 1];
        // cerr << "v: " << v + 1 << ", u: " << u + 1 << '\n';
        lca1[i] = getLca1(v, u);
        lca2[i] = getLca2(v, u);
        comp1[k + i] = lca1[i];
        if (comproot1 == -1 || tin1[comproot1] > tin1[lca1[i]]) {
            comproot1 = lca1[i];
        }
        if (comproot2 == -1 || tin2[comproot2] > tin2[lca2[i]]) {
            comproot2 = lca2[i];
        }
    }
    sort(comp1.begin(), comp1.end(), [&](const int& A, const int& B) {
        return tin1[A] < tin1[B];
    });
    comp1.resize(unique(comp1.begin(), comp1.end()) - comp1.begin());
    for (int i = 0; i < (int)comp1.size(); ++i) {
        newV1[comp1[i]] = i;
    }
    for (int i = 0; i < k - 1; ++i) {
        cout << "? " << vset[i] + 1 << ' ' << vset[i + 1] + 1 << '\n';
    }
    cout << "!" << endl;
    for (int i = 0; i < k - 1; ++i) {
        int v = vset[i], u = vset[i + 1];
        int d1v, d1u, d2v, d2u;
        cin >> d1v >> d1u >> d2v >> d2u;
        int newlca1 = newV1[lca1[i]], newlca2 = tin2[lca2[i]];
        w1[newlca1].emplace_back(newV1[v], d1v);
        w1[newlca1].emplace_back(newV1[u], d1u);
        w1[newV1[v]].emplace_back(newlca1, -d1v);
        w1[newV1[u]].emplace_back(newlca1, -d1u);
        w2[newlca2].emplace_back(tin2[v], d2v);
        w2[newlca2].emplace_back(tin2[u], d2u);
        w2[tin2[v]].emplace_back(newlca2, -d2v);
        w2[tin2[u]].emplace_back(newlca2, -d2u);
    }
    dist1[newV1[comproot1]] = 0;
    tt = 1;
    dfsCalc1(newV1[comproot1]);
    dist2[tin2[comproot2]] = 0;
    ++tt;
    dfsCalc2(tin2[comproot2]);
    vector<int> part1(t), part2(t);
    for (int i = 0; i < t; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        part1[i] = -2ll * dist1[newV1[getLca1(v, u)]] + dist1[newV1[v]] + dist1[newV1[u]];
        part2[i] = -2ll * dist2[tin2[getLca2(v, u)]] + dist2[tin2[v]] + dist2[tin2[u]];
    }
    for (int i = 0; i < t; ++i) {
        cout << part1[i] << ' ' << part2[i] << '\n';
    }
    cout << endl;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
#ifdef LOCALa
    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: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24