Submission #805550

#	Time	Username	Problem	Language	Result	Execution time	Memory
805550		rnl42	Prize (CEOI22_prize)	C++14	100 / 100	3194 ms	432556 KiB

Main

    #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::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
        auto tbegin = chrono::high_resolution_clock::now();

        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);
        assert(queries.size() == K-1);
        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;
     
        vector<pair<int,int>> ans(T);
        for (int i = 0; i < T; i ++) {
            int p, q;
            cin >> p >> q;
            p --; q --;
     
            ans[i] = make_pair(tree1.distance(p, q), tree2.distance(p, q));
        }
        for (int i = 0; i < T; i++) {
            cout << ans[i].first << " " << ans[i].second << '\n';
        }
     
        cout << flush;
    }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:162:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  162 |         assert(queries.size() == K-1);
      |                ~~~~~~~~~~~~~~~^~~~~~
Main.cpp:130:14: warning: variable 'tbegin' set but not used [-Wunused-but-set-variable]
  130 |         auto tbegin = chrono::high_resolution_clock::now();
      |              ^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24