oj.uz

Submission #691807

# Submission time Handle Problem Language Result Execution time Memory
691807 2023-01-31T15:26:28 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2388 ms 290004 KB 
#include <bits/stdc++.h>

using namespace std;

struct Tree {
    vector<int> tin, tout, par, depth, jump;
    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.at(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.at(v)) {
            if (dist.at(to) == -1) {
                dist[to] = dist[v] + w;
                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(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();

    if (max(root1, root2) >= n) {
        while (true) {
            cout << "valeraaa" << endl;
        }
    }

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

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

            if (any[to] != -1) {
                if (any[v] != -1) {
                    questions.emplace_back(any[v], any[to]);
                }
                any[v] = any[to];
            }
        }
    };

    dfs(root2);

    if (questions.size() > q) {
        while (true) {
            cout << "axaxax" << endl;
        }
    }
    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) {
        if (x == y) {
            return;
        }
        (t == 0 ? g1.at(x) : g2.at(x)).emplace_back(y, w);
        (t == 0 ? g1.at(y) : g2.at(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] - 2 * first[t1.lca(a, b)] + first[b];
        int dist2 = second[a] - 2 * second[t2.lca(a, b)] + second[b];

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

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:158:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  158 |     if (questions.size() > q) {
      |         ~~~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 149132 KB Output is correct
2 Correct 1242 ms 153276 KB Output is correct
3 Correct 784 ms 97208 KB Output is correct
4 Correct 777 ms 96100 KB Output is correct
5 Correct 897 ms 100168 KB Output is correct
6 Correct 1222 ms 108996 KB Output is correct
7 Correct 1248 ms 109064 KB Output is correct
8 Correct 1226 ms 107992 KB Output is correct
9 Correct 974 ms 96896 KB Output is correct
10 Correct 968 ms 99300 KB Output is correct
11 Correct 801 ms 94480 KB Output is correct
12 Correct 886 ms 98624 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1226 ms 153116 KB Output is correct
2 Correct 1256 ms 145900 KB Output is correct
3 Runtime error 759 ms 102812 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 848 ms 141288 KB Output is correct
2 Correct 935 ms 141296 KB Output is correct
3 Runtime error 633 ms 92968 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 1997 ms 282268 KB Output is correct
2 Correct 2001 ms 282292 KB Output is correct
3 Runtime error 1206 ms 189508 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 2367 ms 290004 KB Output is correct
2 Correct 2388 ms 289416 KB Output is correct
3 Runtime error 1413 ms 189504 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -