oj.uz

Submission #691770

# Submission time Handle Problem Language Result Execution time Memory
691770 2023-01-31T14:18:24 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2968 ms 434612 KB 
#include <bits/stdc++.h>

using namespace std;

void massert(bool f) {
    while (!f) {
        cout << "hell nah" << endl;
    }
}

struct Tree {
    vector<int> tin, tout, par;
    vector<vector<int>> jump;
    int logn;

    void init(vector<vector<int>> adj, int root) {
        int n = adj.size();
        tin.resize(n), tout.resize(n), par.assign(n, -1);
        int T = 0;

        function<void(int)> dfs = [&](int v) {
            tin[v] = T++;
            for (int to : adj[v]) {
                assert(par[to] == -1);
                par[to] = v;
                dfs(to);
            }
            tout[v] = T;
        };

        dfs(root);

        par[root] = root;

        logn = __lg(n) + 1;

        jump = vector(logn, vector<int>(n));
        jump[0] = par;

        for (int j = 1; j < logn; ++j) {
            for (int i = 0; i < n; ++i) {
                jump[j][i] = jump[j - 1][jump[j - 1][i]];
            }
        }
    }

    bool isp(int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }

    int lca(int a, int b) {
        if (isp(a, b)) {
            return a;
        }

        for (int i = logn - 1; i >= 0; --i) {
            if (!isp(jump[i][a], b)) {
                a = jump[i][a];
            }
        }

        return jump[0][a];
    }
} t1, t2;

vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
    vector<int> dist(n, -1);
    dist[root] = 0;

    function<void(int)> dfs = [&](int v) {
        for (auto [to, w] : g[v]) {
            if (dist[to] == -1) {
                dist[to] = dist[v] + w;
                massert(dist[to] != -1);
                dfs(to);
            }
        }
    };

    dfs(root);

    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q, t;
    cin >> n >> k >> q >> t;

    vector<int> p1(n), p2(n);

    for (int i = 0; i < n; ++i) {
        cin >> p1[i];
        p1[i] = max(-1, p1[i] - 1);
    }

    for (int i = 0; i < n; ++i) {
        cin >> p2[i];
        p2[i] = max(-1, p2[i] - 1);
    }

    for (int i = 1; i <= k; ++i) {
        cout << i << " ";
    }
    cout << endl;

    int root1 = find(p1.begin(), p1.end(), -1) - p1.begin();
    int root2 = find(p2.begin(), p2.end(), -1) - p2.begin();

    vector<vector<int>> adj(n);

    for (int i = 0; i < n; ++i) {
        if (p1[i] != -1) {
            adj[p1[i]].push_back(i);
        }
    }

    t1.init(adj, root1);

    for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }

    for (int i = 0; i < n; ++i) {
        if (p2[i] != -1) {
            adj[p2[i]].push_back(i);
        }
    }

    t2.init(adj, root2);

    vector<pair<int, int>> questions;

    vector<int> any(n, -1);

    function<void(int)> dfs = [&](int v) {
        if (v < k) {
            any[v] = v;
        }

        vector<int> alive;

        for (int to : adj[v]) {
            dfs(to);

            if (any[to] != -1) {
                alive.push_back(to);
            }
        }

        if (alive.empty()) {
            return;
        }

        any[v] = any[alive[0]];

        if (alive.size() == 1) {
            if (v < k) {
                questions.emplace_back(any[alive[0]], v);
            }
        } else {
            for (int i = 1; i < alive.size(); ++i) {
                questions.emplace_back(any[alive[0]], any[alive[i]]);
            }
        }
    };

    dfs(root2);

    for (auto [x, y] : questions) {
        cout << "? " << x + 1 << " " << y + 1 << endl;
    }
    cout << "!" << endl;

    vector<vector<pair<int, int>>> g1(n), g2(n);

    int h1 = -1, h2 = -1;

    auto addEdge = [&](int t, int x, int y, int w) {
        (t == 0 ? g1[x] : g2[x]).emplace_back(y, w);
        (t == 0 ? g1[y] : g2[y]).emplace_back(x, -w);
    };

    for (auto [x, y] : questions) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int c1 = t1.lca(x, y);
        int c2 = t2.lca(x, y);

        if (h1 == -1 || t1.isp(c1, h1)) {
            h1 = c1;
        }
        if (h2 == -1 || t2.isp(c2, h2)) {
            h2 = c2;
        }

        addEdge(0, c1, x, a);
        addEdge(0, c1, y, b);
        addEdge(1, c2, x, c);
        addEdge(1, c2, y, d);
    }

    auto first = normalize(n, h1, g1);
    auto second = normalize(n, h2, g2);

    vector<pair<int, int>> queries(t);
    for (auto &[a, b] : queries) {
        cin >> a >> b;
        a -= 1, b -= 1;
    }

    for (auto [a, b] : queries) {
        int dist1 = first[a] + first[b] - 2 * first[t1.lca(a, b)];
        int dist2 = second[a] + second[b] - 2 * second[t2.lca(a, b)];

        cout << dist1 << " " << dist2 << '\n';
    }

    return 0;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:164:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             for (int i = 1; i < alive.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 217700 KB Output is correct
2 Correct 1571 ms 221764 KB Output is correct
3 Correct 1060 ms 163644 KB Output is correct
4 Correct 1008 ms 162844 KB Output is correct
5 Correct 1267 ms 166996 KB Output is correct
6 Correct 1644 ms 175924 KB Output is correct
7 Correct 1797 ms 175884 KB Output is correct
8 Correct 1646 ms 174852 KB Output is correct
9 Correct 1344 ms 163268 KB Output is correct
10 Correct 1324 ms 166284 KB Output is correct
11 Correct 1136 ms 161248 KB Output is correct
12 Correct 1284 ms 165536 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1797 ms 220556 KB Output is correct
2 Correct 1537 ms 214192 KB Output is correct
3 Runtime error 902 ms 167220 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 207864 KB Output is correct
2 Correct 1049 ms 207968 KB Output is correct
3 Runtime error 620 ms 159492 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2559 ms 423124 KB Output is correct
2 Correct 2402 ms 423128 KB Output is correct
3 Runtime error 1348 ms 330332 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2968 ms 434612 KB Output is correct
2 Correct 2859 ms 434508 KB Output is correct
3 Runtime error 1723 ms 330516 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -