oj.uz

답안 #915829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915829 2024-01-24T18:45:06 Z Alcabel Prize (CEOI22_prize) C++17
54 / 100
 3500 ms 396968 KB 
#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], 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];
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);
    }
}

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];
    });
    dsu = DSU(n);
    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();
    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();
    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();
    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 2183 ms 273764 KB Output is correct
2 Correct 2392 ms 277396 KB Output is correct
3 Correct 1192 ms 173516 KB Output is correct
4 Correct 1230 ms 172992 KB Output is correct
5 Correct 1242 ms 176676 KB Output is correct
6 Correct 1834 ms 194472 KB Output is correct
7 Correct 1709 ms 190840 KB Output is correct
8 Correct 1721 ms 188648 KB Output is correct
9 Correct 1201 ms 173340 KB Output is correct
10 Correct 1217 ms 176260 KB Output is correct
11 Correct 1124 ms 171424 KB Output is correct
12 Correct 1187 ms 174664 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2170 ms 277684 KB Output is correct
2 Correct 2114 ms 272196 KB Output is correct
3 Correct 1253 ms 174336 KB Output is correct
4 Correct 1218 ms 177292 KB Output is correct
5 Correct 1199 ms 175016 KB Output is correct
6 Correct 1682 ms 192040 KB Output is correct
7 Correct 1616 ms 196016 KB Output is correct
8 Correct 1639 ms 196452 KB Output is correct
9 Correct 1427 ms 195460 KB Output is correct
10 Correct 1548 ms 196060 KB Output is correct
11 Correct 1372 ms 191596 KB Output is correct
12 Correct 1487 ms 195976 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1873 ms 263592 KB Output is correct
2 Correct 1794 ms 263428 KB Output is correct
3 Correct 903 ms 162340 KB Output is correct
4 Correct 1000 ms 162568 KB Output is correct
5 Correct 989 ms 162884 KB Output is correct
6 Correct 1280 ms 183280 KB Output is correct
7 Correct 1294 ms 183176 KB Output is correct
8 Correct 1335 ms 182464 KB Output is correct
9 Correct 1228 ms 180732 KB Output is correct
10 Correct 1389 ms 180416 KB Output is correct
11 Correct 1157 ms 180644 KB Output is correct
12 Correct 1268 ms 180696 KB Output is correct

Subtask #4
0 / 22.0

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

Subtask #5
0 / 24.0

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