oj.uz

Submission #691771

# Submission time Handle Problem Language Result Execution time Memory
691771 2023-01-31T14:18:43 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2771 ms 434504 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]) {
                massert(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 1628 ms 217616 KB Output is correct
2 Correct 1635 ms 221532 KB Output is correct
3 Correct 1342 ms 163508 KB Output is correct
4 Correct 1297 ms 162824 KB Output is correct
5 Correct 1388 ms 167000 KB Output is correct
6 Correct 1848 ms 175904 KB Output is correct
7 Correct 1824 ms 175968 KB Output is correct
8 Correct 1894 ms 174944 KB Output is correct
9 Correct 1270 ms 163348 KB Output is correct
10 Correct 1389 ms 166232 KB Output is correct
11 Correct 1284 ms 161232 KB Output is correct
12 Correct 1345 ms 165492 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 220604 KB Output is correct
2 Correct 1579 ms 214260 KB Output is correct
3 Runtime error 973 ms 167292 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 1097 ms 207848 KB Output is correct
2 Correct 1033 ms 207920 KB Output is correct
3 Runtime error 665 ms 159672 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 2505 ms 423232 KB Output is correct
2 Correct 2422 ms 423188 KB Output is correct
3 Runtime error 1398 ms 330460 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 2771 ms 434504 KB Output is correct
2 Correct 2663 ms 434504 KB Output is correct
3 Runtime error 1583 ms 330456 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -