oj.uz

Submission #916030

# Submission time Handle Problem Language Result Execution time Memory
916030 2024-01-25T07:16:20 Z Alcabel Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 416404 KB 
#pragma GCC optimize("O3", "Ofast")
// #pragma GCC optimize("avx", "avx2")
#include <bits/stdc++.h>
using namespace std;
 
struct DSU {
    int n;
    vector<int> par, sz;
    vector<pair<int, int>> minH;
    DSU() {}
    DSU(int _n) {
        n = _n;
        par.resize(n);
        sz.resize(n);
        minH.resize(n);
        clear();
    }
    void clear() {
        for (int i = 0; i < n; ++i) {
            par[i] = i, sz[i] = 1;
        }
    }
    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[v], minH[u]);
    }
    ~DSU() {}
};
 
const int maxn = 1e6;
vector<int> g1[maxn], g2[maxn];
int tin1[maxn], tin2[maxn], tt;

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]) {
        dfs1(u, k);
    }
}
 
void dfs2(int v) {
    tin2[v] = tt++;
    for (const int& u : g2[v]) {
        dfs2(u);
    }
}
 
vector<pair<int, int>> queries[maxn];
const int maxq = 1e5;
int ans[maxq];
DSU dsu;
 
void dfsAns1(int v) {
    while (!queries[v].empty()) {
        ans[queries[v].back().second] = dsu.getminH(queries[v].back().first);
        queries[v].pop_back();
    }
    for (const int& u : g1[v]) {
        dfsAns1(u);
        dsu.uniteSets(v, u);
    }
}
 
void dfsAns2(int v) {
    while (!queries[v].empty()) {
        ans[queries[v].back().second] = dsu.getminH(queries[v].back().first);
        queries[v].pop_back();
    }
    for (const int& u : g2[v]) {
        dfsAns2(u);
        dsu.uniteSets(v, u);
    }
}

// int newV1[maxn];
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) {
        // newV1[i] = -1;
        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;
        }
    }
    // tin2[v] <=> newV2[v], newV1[v] <=> sorted lca1 + vset
    tt = 0;
    dfs2(root2);
    tt = 0;
    dfs1(root1, k);
    for (const int& v : vset) {
        cout << v + 1 << ' ';
    }
    cout << endl;
    dsu = DSU(n);
    for (int i = 0; i < n; ++i) {
        dsu.minH[i] = {tin1[i], i};
    }
    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);
    }
    dsu.clear();
    for (int i = 0; i < n; ++i) {
        dsu.minH[i] = {tin2[i], 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);
    dsu.clear();
    for (int i = 0; i < n; ++i) {
        dsu.minH[i] = {tin1[i], i};
    }
    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);
    }
    dsu.clear();
    for (int i = 0; i < n; ++i) {
        dsu.minH[i] = {tin2[i], 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 2015 ms 279628 KB Output is correct
2 Correct 2252 ms 283008 KB Output is correct
3 Correct 1232 ms 172256 KB Output is correct
4 Correct 1216 ms 171108 KB Output is correct
5 Correct 1293 ms 174356 KB Output is correct
6 Correct 1443 ms 194064 KB Output is correct
7 Correct 1696 ms 194156 KB Output is correct
8 Correct 1702 ms 193876 KB Output is correct
9 Correct 1250 ms 171904 KB Output is correct
10 Correct 1293 ms 174220 KB Output is correct
11 Correct 1244 ms 169868 KB Output is correct
12 Correct 1224 ms 172740 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2179 ms 283684 KB Output is correct
2 Correct 2282 ms 278744 KB Output is correct
3 Correct 1209 ms 172032 KB Output is correct
4 Correct 1389 ms 175440 KB Output is correct
5 Correct 1414 ms 173164 KB Output is correct
6 Correct 1604 ms 191644 KB Output is correct
7 Correct 1478 ms 195892 KB Output is correct
8 Correct 1708 ms 196180 KB Output is correct
9 Correct 1685 ms 194716 KB Output is correct
10 Correct 1647 ms 195760 KB Output is correct
11 Correct 1529 ms 191100 KB Output is correct
12 Correct 1471 ms 196108 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2061 ms 269860 KB Output is correct
2 Correct 1943 ms 269660 KB Output is correct
3 Correct 1077 ms 161204 KB Output is correct
4 Correct 917 ms 160412 KB Output is correct
5 Correct 1004 ms 160640 KB Output is correct
6 Correct 1439 ms 182108 KB Output is correct
7 Correct 1290 ms 181908 KB Output is correct
8 Correct 1354 ms 182168 KB Output is correct
9 Correct 1120 ms 179836 KB Output is correct
10 Correct 1168 ms 179696 KB Output is correct
11 Correct 1202 ms 180084 KB Output is correct
12 Correct 1172 ms 179844 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3584 ms 404320 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 3590 ms 416404 KB Time limit exceeded
2 Halted 0 ms 0 KB -