oj.uz

Submission #804526

# Submission time Handle Problem Language Result Execution time Memory
804526 2023-08-03T09:32:14 Z thimote75 Prize (CEOI22_prize) C++14
0 / 100
 2692 ms 431712 KB 
#include <bits/stdc++.h>

using namespace std;

using bdata = vector<bool>;
using idata = vector<int>;
using igrid = vector<idata>;

const int MAXK = 21;

struct Tree {
    igrid roads;
    igrid parents_2k;
    idata dist_root;
    idata parents;
    idata preordre;
    idata depth;
    int root;

    void dfs_preordre (int node, int _depth) {
        preordre.push_back(node);
        depth[node] = _depth;

        for (int next : roads[node])
            dfs_preordre(next, _depth + 1);
    }

    int jump (int node, int k) {
        for (int i = 0; i < MAXK; i ++) {
            if (((1 << i) & k) == 0) continue ;

            node = parents_2k[node][i];
        }

        return node;
    }
    int lca (int a, int b) {
        if (depth[a] > depth[b]) swap(a, b);

        b = jump(b, depth[b] - depth[a]);
        if (a == b) return a;

        for (int i = MAXK - 1; i >= 0; i --) {
            if (parents_2k[a][i] == parents_2k[b][i]) continue ;

            a = parents_2k[a][i];
            b = parents_2k[b][i];
        }

        return parents[a];
    }
    int distance (int a, int b) {
        int l = lca(a, b);

        return dist_root[a] + dist_root[b] - 2 * dist_root[l];
    }

    void dfs_compute (idata &distances_to_parent, int distance, int node) {
        distance += distances_to_parent[node];
        dist_root[node] = distance;

        for (int next : roads[node])
            dfs_compute(distances_to_parent, distance, next);
    }
    void compute (idata &distances_to_parent) {
        dfs_compute(distances_to_parent, 0, root);
    }

    Tree () = default;
    Tree (int N) {
        dist_root.resize(N, -1);
        roads    .resize(N);
        depth    .resize(N);
        parents  .resize(N);

        for (int i = 0; i < N; i ++) {
            cin >> parents[i];
            parents[i] --;

            if (parents[i] == -2) {
                parents[i] = -1;
                root = i;

                continue ;
            }

            roads[parents[i]].push_back(i);
        }

        dfs_preordre(root, 0);
    }
    void init_lca (int N) {
        parents_2k.resize(N, idata(MAXK, -1));
        for (int i = 0; i < N; i ++)
            parents_2k[i][0] = parents[i];
        
        for (int k = 0; k + 1 < MAXK; k ++) {
            for (int i = 0; i < N; i ++) {
                if (parents_2k[i][k] == -1) continue ;

                parents_2k[i][k + 1] = parents_2k[parents_2k[i][k]][k];
            }
        }
    }
};

Tree tree1, tree2;
bdata subset;

vector<pair<int, int>> queries;

int last_preordre = -1;
void dfs_query (int node) {
    if (subset[node]) {
        if (last_preordre != -1) {
            queries.push_back({ last_preordre, node });

            cout << "? " << last_preordre + 1 << " " << node + 1 << "\n";
        }
        last_preordre = node;
    }

    for (int next : tree1.roads[node])
        dfs_query(next);
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, K, Q, T;
    cin >> N >> K >> Q >> T;

    tree1 = Tree(N);
    tree2 = Tree(N);

    subset.resize(N);

    for (int i = 0; i < K; i ++) {
        subset[ tree2.preordre[i] ] = true;

        cout << tree2.preordre[i] + 1;

        if (i + 1 == K) cout << "\n";
        else cout << " ";
    }

    cout << flush;

    dfs_query(tree1.root);

    cout << "!\n";
    cout << flush;

    tree1.init_lca(N);
    tree2.init_lca(N);

    idata distance_to_root1(N, 0);
    idata distance_to_root2(N, 0);
    for (const auto &query : queries) {
        int q1 = query.first;
        int q2 = query.second;

        int al1, bl1, al2, bl2;
        cin >> al1 >> bl1 >> al2 >> bl2;

        int lca1 = tree1.lca(q1, q2);
        int lca2 = tree2.lca(q1, q2);
        distance_to_root1[lca1] = distance_to_root1[q1]       - al1;
        distance_to_root1[q2  ] = distance_to_root1[q1] + bl1 - al1;

        distance_to_root2[lca2] = distance_to_root2[q1]       - al2;
        distance_to_root2[q2  ] = distance_to_root2[q1] + bl2 - al2;
    }

    tree1.dist_root = distance_to_root1;
    tree2.dist_root = distance_to_root2;

    for (int i = 0; i < T; i ++) {
        int p, q;
        cin >> p >> q;
        p --; q --;

        cout << tree1.distance(p, q) << " " << tree2.distance(p, q) << "\n";
    }

    cout << flush;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1221 ms 216264 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1326 ms 216412 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 215692 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2316 ms 431020 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2692 ms 431712 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -