oj.uz

답안 #916026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916026 2024-01-25T07:14:15 Z Alcabel Prize (CEOI22_prize) C++17
10 / 100
 3500 ms 416684 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] = {tin1[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

# 결과 실행 시간 메모리 Grader output
1 Correct 2161 ms 279756 KB Output is correct
2 Correct 2208 ms 283800 KB Output is correct
3 Correct 1087 ms 171688 KB Output is correct
4 Correct 1155 ms 171604 KB Output is correct
5 Correct 1110 ms 175012 KB Output is correct
6 Correct 1461 ms 194348 KB Output is correct
7 Correct 1512 ms 194248 KB Output is correct
8 Correct 1438 ms 192748 KB Output is correct
9 Correct 1166 ms 171884 KB Output is correct
10 Correct 1093 ms 174076 KB Output is correct
11 Correct 1066 ms 169668 KB Output is correct
12 Correct 1197 ms 173420 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2048 ms 284168 KB Output is correct
2 Correct 1922 ms 278560 KB Output is correct
3 Runtime error 1063 ms 171440 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1808 ms 269920 KB Output is correct
2 Correct 1768 ms 269856 KB Output is correct
3 Runtime error 811 ms 160216 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3570 ms 404620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3612 ms 416684 KB Time limit exceeded
2 Halted 0 ms 0 KB -