oj.uz

Submission #691793

# Submission time Handle Problem Language Result Execution time Memory
691793 2023-01-31T14:59:19 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2602 ms 380104 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

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

constexpr int N = 1e6 + 1;

struct Tree {
    vector<int> tin, tout, par, depth, jump;
//    static int tin[N], tout[N], par[N], depth[N];
//    static int jump[N];
    int logn;

    void init(vector<vector<int>> adj, int root) {
        int n = adj.size();
        int T = 0;

        tin.resize(n), tout.resize(n), par.resize(n), depth.resize(n), jump.resize(n);

        par[root] = jump[root] = root;

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

                int p = jump[v];
                int pp = jump[p];
                if (depth[p] - depth[v] == depth[pp] - depth[p]) {
                    jump[to] = pp;
                } else {
                    jump[to] = v;
                }

                dfs(to);
            }
            tout[v] = T;
        };

        dfs(root);


        logn = __lg(n) + 1;
    }

    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;
        }

        while (!isp(par[a], b)) {
            if (isp(jump[a], b)) {
                a = par[a];
            } else {
                a = jump[a];
            }
        }

        return par[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;
}

int32_t 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(int(-1), p1[i] - 1);
    }

    for (int i = 0; i < n; ++i) {
        cin >> p2[i];
        p2[i] = max(int(-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);
    vector<bool> used(n);

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

        vector<int> alive;

        for (int to : adj[v]) {
            massert(!used[to]);
            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);

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

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

    int h1 = 0, h2 = 0;

    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 (t1.isp(c1, h1)) {
            h1 = c1;
        }
        if (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:178:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |             for (int i = 1; i < alive.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:186:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  186 |     massert(questions.size() <= q);
      |             ~~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1326 ms 194892 KB Output is correct
2 Correct 1403 ms 202852 KB Output is correct
3 Correct 955 ms 134412 KB Output is correct
4 Correct 875 ms 133348 KB Output is correct
5 Correct 982 ms 140012 KB Output is correct
6 Correct 1235 ms 149164 KB Output is correct
7 Correct 1243 ms 149100 KB Output is correct
8 Correct 1229 ms 147492 KB Output is correct
9 Correct 855 ms 133872 KB Output is correct
10 Correct 944 ms 138896 KB Output is correct
11 Correct 866 ms 131816 KB Output is correct
12 Correct 969 ms 137740 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1625 ms 201916 KB Output is correct
2 Correct 1312 ms 191708 KB Output is correct
3 Runtime error 760 ms 139272 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 898 ms 184516 KB Output is correct
2 Correct 899 ms 184436 KB Output is correct
3 Runtime error 579 ms 129264 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 2154 ms 368420 KB Output is correct
2 Correct 2115 ms 368304 KB Output is correct
3 Runtime error 1269 ms 258048 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 2602 ms 380104 KB Output is correct
2 Correct 2421 ms 377324 KB Output is correct
3 Runtime error 1440 ms 265952 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -