oj.uz

답안 #916054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916054 2024-01-25T08:12:16 Z Alcabel Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 347080 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;
    DSU() {}
    DSU(int _n) {
        n = _n;
        par.resize(n);
        clear();
    }
    void clear() {
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }
    int getParent(int v) {
        if (par[v] != v) {
            par[v] = getParent(par[v]);
        }
        return par[v];
    }
    void uniteSets(int v, int u) {
        v = getParent(v), u = getParent(u);
        if (v == u) {
            return;
        }
        par[u] = v;
    }
    ~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.getParent(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.getParent(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[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;
        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), comp1(2 * k - 1);
    for (int i = 0; i < k; ++i) {
        comp1[i] = vset[i];
    }
    for (int i = 0; i < k - 1; ++i) {
        comp1[k + i] = ans[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);
    }
    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;
    }
    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;
        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<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[newV1[ans[i]]] + dist1[newV1[v]] + dist1[newV1[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[tin2[ans[i]]] + dist2[tin2[v]] + dist2[tin2[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 1782 ms 223052 KB Output is correct
2 Correct 1771 ms 226696 KB Output is correct
3 Correct 978 ms 123688 KB Output is correct
4 Correct 859 ms 122028 KB Output is correct
5 Correct 940 ms 126296 KB Output is correct
6 Correct 1249 ms 143972 KB Output is correct
7 Correct 1251 ms 144192 KB Output is correct
8 Correct 1257 ms 142956 KB Output is correct
9 Correct 857 ms 122708 KB Output is correct
10 Correct 883 ms 125016 KB Output is correct
11 Correct 898 ms 121120 KB Output is correct
12 Correct 922 ms 124536 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1687 ms 226916 KB Output is correct
2 Correct 1892 ms 221712 KB Output is correct
3 Correct 919 ms 123404 KB Output is correct
4 Correct 946 ms 126860 KB Output is correct
5 Correct 853 ms 124300 KB Output is correct
6 Correct 1263 ms 141620 KB Output is correct
7 Correct 1362 ms 146052 KB Output is correct
8 Correct 1416 ms 146396 KB Output is correct
9 Correct 1270 ms 144292 KB Output is correct
10 Correct 1152 ms 145840 KB Output is correct
11 Correct 1093 ms 141220 KB Output is correct
12 Correct 1151 ms 145496 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1528 ms 212372 KB Output is correct
2 Correct 1725 ms 212276 KB Output is correct
3 Correct 696 ms 111432 KB Output is correct
4 Correct 760 ms 111204 KB Output is correct
5 Correct 663 ms 111308 KB Output is correct
6 Correct 1090 ms 131304 KB Output is correct
7 Correct 988 ms 131312 KB Output is correct
8 Correct 1062 ms 131064 KB Output is correct
9 Correct 909 ms 129032 KB Output is correct
10 Correct 924 ms 129056 KB Output is correct
11 Correct 871 ms 129076 KB Output is correct
12 Correct 842 ms 129456 KB Output is correct

Subtask #4
0 / 22.0

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

Subtask #5
0 / 24.0

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