oj.uz

Submission #805629

# Submission time Handle Problem Language Result Execution time Memory
805629 2023-08-03T19:04:45 Z rnl42 Prize (CEOI22_prize) C++14
0 / 100
 2763 ms 431708 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);
    
    char* bufcout = new char[20000000];
    cout.rdbuf()->pubsetbuf(bufcout, 20000000);


    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 1077 ms 216192 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 1246 ms 216448 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 983 ms 215816 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 2337 ms 431136 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 2763 ms 431708 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -