oj.uz

Submission #691767

# Submission time Handle Problem Language Result Execution time Memory
691767 2023-01-31T14:15:23 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2619 ms 434524 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;
                assert(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 1380 ms 217888 KB Output is correct
2 Correct 1505 ms 221628 KB Output is correct
3 Correct 1120 ms 163700 KB Output is correct
4 Correct 1090 ms 162808 KB Output is correct
5 Correct 1428 ms 167016 KB Output is correct
6 Correct 1825 ms 175940 KB Output is correct
7 Correct 1656 ms 175856 KB Output is correct
8 Correct 1584 ms 174920 KB Output is correct
9 Correct 1220 ms 163292 KB Output is correct
10 Correct 1239 ms 166292 KB Output is correct
11 Correct 1089 ms 161200 KB Output is correct
12 Correct 1124 ms 165496 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1550 ms 220844 KB Output is correct
2 Correct 1452 ms 214188 KB Output is correct
3 Runtime error 899 ms 167248 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 924 ms 207900 KB Output is correct
2 Correct 936 ms 208084 KB Output is correct
3 Runtime error 568 ms 159588 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 2294 ms 423384 KB Output is correct
2 Correct 2237 ms 423200 KB Output is correct
3 Runtime error 1239 ms 330452 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 2619 ms 434512 KB Output is correct
2 Correct 2549 ms 434524 KB Output is correct
3 Runtime error 1484 ms 330484 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -