oj.uz

Submission #916082

# Submission time Handle Problem Language Result Execution time Memory
916082 2024-01-25T09:07:39 Z Alcabel Prize (CEOI22_prize) C++17
100 / 100
 2156 ms 228620 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 159764 KB Output is correct
2 Correct 1047 ms 164288 KB Output is correct
3 Correct 595 ms 115584 KB Output is correct
4 Correct 526 ms 115532 KB Output is correct
5 Correct 686 ms 118168 KB Output is correct
6 Correct 773 ms 127004 KB Output is correct
7 Correct 925 ms 126768 KB Output is correct
8 Correct 814 ms 124160 KB Output is correct
9 Correct 559 ms 115716 KB Output is correct
10 Correct 658 ms 118036 KB Output is correct
11 Correct 566 ms 112220 KB Output is correct
12 Correct 620 ms 115780 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 164716 KB Output is correct
2 Correct 879 ms 159660 KB Output is correct
3 Correct 678 ms 114888 KB Output is correct
4 Correct 750 ms 117856 KB Output is correct
5 Correct 704 ms 116748 KB Output is correct
6 Correct 812 ms 124280 KB Output is correct
7 Correct 900 ms 127236 KB Output is correct
8 Correct 952 ms 127728 KB Output is correct
9 Correct 790 ms 126008 KB Output is correct
10 Correct 848 ms 126940 KB Output is correct
11 Correct 729 ms 122380 KB Output is correct
12 Correct 826 ms 126836 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 153604 KB Output is correct
2 Correct 685 ms 153228 KB Output is correct
3 Correct 412 ms 106748 KB Output is correct
4 Correct 478 ms 106916 KB Output is correct
5 Correct 400 ms 106900 KB Output is correct
6 Correct 528 ms 116044 KB Output is correct
7 Correct 549 ms 116700 KB Output is correct
8 Correct 599 ms 115508 KB Output is correct
9 Correct 486 ms 113964 KB Output is correct
10 Correct 534 ms 115232 KB Output is correct
11 Correct 508 ms 113864 KB Output is correct
12 Correct 483 ms 113504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1544 ms 217588 KB Output is correct
2 Correct 1607 ms 218564 KB Output is correct
3 Correct 1184 ms 124932 KB Output is correct
4 Correct 1137 ms 125532 KB Output is correct
5 Correct 1150 ms 125060 KB Output is correct
6 Correct 1428 ms 144900 KB Output is correct
7 Correct 1503 ms 145292 KB Output is correct
8 Correct 1488 ms 144800 KB Output is correct
9 Correct 1337 ms 140896 KB Output is correct
10 Correct 1328 ms 140420 KB Output is correct
11 Correct 1251 ms 140680 KB Output is correct
12 Correct 1268 ms 141016 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2156 ms 228620 KB Output is correct
2 Correct 2052 ms 228284 KB Output is correct
3 Correct 1288 ms 133200 KB Output is correct
4 Correct 1413 ms 137728 KB Output is correct
5 Correct 1294 ms 132032 KB Output is correct
6 Correct 1958 ms 157412 KB Output is correct
7 Correct 1756 ms 152332 KB Output is correct
8 Correct 1874 ms 154772 KB Output is correct
9 Correct 1587 ms 150548 KB Output is correct
10 Correct 1611 ms 148820 KB Output is correct
11 Correct 1610 ms 149376 KB Output is correct
12 Correct 1625 ms 151720 KB Output is correct