oj.uz

Submission #915848

# Submission time Handle Problem Language Result Execution time Memory
915848 2024-01-24T19:03:46 Z Alcabel Prize (CEOI22_prize) C++17
35 / 100
 3500 ms 314460 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6;
int par[maxn], sz[maxn];
pair<int, int> minH[maxn];

int getParent(int v) {
    if (par[v] != v) {
        par[v] = getParent(par[v]);
    }
    return par[v];
}

int getMinH(int v) {
    return minH[getParent(v)].second;
}
    
void uniteSets(int v, int u) {
    v = getParent(v), u = getParent(u);
    if (v == u) {
        return;
    }
    if (sz[v] < sz[u]) {
        swap(v, u);
    }
    sz[v] += sz[u];
    par[u] = v;
    minH[v] = min(minH[u], minH[v]);
}

vector<int> g1[maxn], g2[maxn];
int tin1[maxn], tout1[maxn], tin2[maxn], tout2[maxn], tt;

void dfs1(int v) {
    tin1[v] = tt++;
    for (const int& u : g1[v]) {
        dfs1(u);
    }
    tout1[v] = tt++;
}

vector<int> vset;

void dfs2(int v, int k) {
    tin2[v] = tt++;
    // cerr << "v: " << v + 1 << '\n';
    if ((int)vset.size() < k) {
        // cerr << "hui\n";
        vset.emplace_back(v);
    }
    for (const int& u : g2[v]) {
        dfs2(u, k);
    }
    tout2[v] = tt++;
}

vector<pair<int, int>> queries[maxn];
const int maxq = 1e5;
int ans[maxq];

void dfsAns1(int v) {
    par[v] = v, sz[v] = 1;
    while (!queries[v].empty()) {
        ans[queries[v].back().second] = getMinH(queries[v].back().first);
        queries[v].pop_back();
    }
    minH[v] = {tin1[v], v};
    for (const int& u : g1[v]) {
        dfsAns1(u);
        uniteSets(v, u);
    }
}

void dfsAns2(int v) {
    par[v] = v, sz[v] = 1;
    while (!queries[v].empty()) {
        ans[queries[v].back().second] = getMinH(queries[v].back().first);
        queries[v].pop_back();
    }
    minH[v] = {tin2[v], v};
    for (const int& u : g2[v]) {
        dfsAns2(u);
        uniteSets(v, u);
    }
}

vector<pair<int, int>> w1[maxn], w2[maxn];
char vis[maxn];
int dist1[maxn], dist2[maxn];

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) {
        int p;
        cin >> p;
        --p;
        if (p != -2) {
            g1[p].emplace_back(i);
        } else {
            root1 = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        --p;
        if (p != -2) {
            g2[p].emplace_back(i);
        } else {
            root2 = i;
        }
    }
    tt = 0;
    dfs1(root1);
    tt = 0;
    dfs2(root2, k);
    for (const int& v : vset) {
        cout << v + 1 << ' ';
    }
    cout << endl;
    sort(vset.begin(), vset.end(), [&](const int& A, const int& B) {
        return tin1[A] < tin1[B];
    });
    for (int i = 0; i < k - 1; ++i) {
        int v = vset[i], u = vset[i + 1];
        // cerr << "v: " << v + 1 << ", u: " << u + 1 << '\n';
        queries[u].emplace_back(v, i);
    }
    dfsAns1(root1);
    int comproot1 = -1;
    vector<int> lca1(k - 1);
    for (int i = 0; i < k - 1; ++i) {
        lca1[i] = ans[i];
        // cerr << "i: " << i << ", lca1: " << lca1[i] + 1 << '\n';
        if (comproot1 == -1 || tin1[comproot1] > tin1[ans[i]]) {
            comproot1 = ans[i];
        }
        int v = vset[i], u = vset[i + 1];
        if (tin2[v] > tin2[u]) {
            swap(v, u);
        }
        queries[u].emplace_back(v, i);
    }
    dfsAns2(root2);
    int comproot2 = -1;
    vector<int> lca2(k - 1);
    for (int i = 0; i < k - 1; ++i) {
        lca2[i] = ans[i];
        // cerr << "i: " << i << ", lca2: " << lca2[i] + 1 << '\n';
        if (comproot2 == -1 || tin2[comproot2] > tin2[ans[i]]) {
            comproot2 = ans[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;
        w1[lca1[i]].emplace_back(v, d1v);
        w1[lca1[i]].emplace_back(u, d1u);
        w1[v].emplace_back(lca1[i], -d1v);
        w1[u].emplace_back(lca1[i], -d1u);
        w2[lca2[i]].emplace_back(v, d2v);
        w2[lca2[i]].emplace_back(u, d2u);
        w2[v].emplace_back(lca2[i], -d2v);
        w2[u].emplace_back(lca2[i], -d2u);
    }
    dist1[comproot1] = 0;
    tt = 1;
    dfsCalc1(comproot1);
    dist2[comproot2] = 0;
    ++tt;
    dfsCalc2(comproot2);
    vector<pair<int, int>> toAsk(t);
    for (int i = 0; i < t; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        toAsk[i] = {v, u};
        if (tin1[v] > tin1[u]) {
            swap(v, u);
        }
        queries[u].emplace_back(v, i);
    }
    vector<int> part1(t), part2(t);
    dfsAns1(root1);
    for (int i = 0; i < t; ++i) {
        // cerr << "i: " << i << ", lca1: " << ans[i] + 1 << '\n';
        auto [v, u] = toAsk[i];
        part1[i] = -2ll * dist1[ans[i]] + dist1[v] + dist1[u];
        if (tin2[v] > tin2[u]) {
            swap(v, u);
        }
        queries[u].emplace_back(v, i);
    }
    dfsAns2(root2);
    for (int i = 0; i < t; ++i) {
        // cerr << "i: " << i << ", lca2: " << ans[i] + 1 << '\n';
        auto [v, u] = toAsk[i];
        part2[i] = -2ll * dist2[ans[i]] + dist2[v] + dist2[u];
        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 2139 ms 236528 KB Output is correct
2 Correct 2304 ms 240452 KB Output is correct
3 Correct 1271 ms 183096 KB Output is correct
4 Correct 1280 ms 182828 KB Output is correct
5 Correct 1302 ms 186300 KB Output is correct
6 Correct 1635 ms 195692 KB Output is correct
7 Correct 1668 ms 195856 KB Output is correct
8 Correct 1598 ms 195164 KB Output is correct
9 Correct 1272 ms 183580 KB Output is correct
10 Correct 1254 ms 185596 KB Output is correct
11 Correct 1240 ms 181596 KB Output is correct
12 Correct 1318 ms 184548 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2059 ms 240620 KB Output is correct
2 Correct 2141 ms 235156 KB Output is correct
3 Correct 1277 ms 184160 KB Output is correct
4 Correct 1368 ms 186904 KB Output is correct
5 Correct 1383 ms 184836 KB Output is correct
6 Correct 1572 ms 193496 KB Output is correct
7 Correct 1708 ms 197516 KB Output is correct
8 Correct 1693 ms 197780 KB Output is correct
9 Correct 1559 ms 196752 KB Output is correct
10 Correct 1561 ms 197732 KB Output is correct
11 Correct 1498 ms 192624 KB Output is correct
12 Correct 1496 ms 197348 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 227088 KB Output is correct
2 Correct 1854 ms 227800 KB Output is correct
3 Runtime error 945 ms 172192 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3552 ms 302556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3550 ms 314460 KB Time limit exceeded
2 Halted 0 ms 0 KB -