oj.uz

Submission #805550

# Submission time Handle Problem Language Result Execution time Memory
805550 2023-08-03T17:46:12 Z rnl42 Prize (CEOI22_prize) C++14
100 / 100
 3194 ms 432556 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::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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1537 ms 217032 KB Output is correct
2 Correct 1584 ms 217224 KB Output is correct
3 Correct 970 ms 178484 KB Output is correct
4 Correct 976 ms 178424 KB Output is correct
5 Correct 916 ms 178616 KB Output is correct
6 Correct 1375 ms 187028 KB Output is correct
7 Correct 1392 ms 187000 KB Output is correct
8 Correct 1448 ms 186968 KB Output is correct
9 Correct 889 ms 178572 KB Output is correct
10 Correct 926 ms 178568 KB Output is correct
11 Correct 819 ms 178324 KB Output is correct
12 Correct 845 ms 178548 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1581 ms 217208 KB Output is correct
2 Correct 1547 ms 216912 KB Output is correct
3 Correct 946 ms 178460 KB Output is correct
4 Correct 941 ms 178624 KB Output is correct
5 Correct 910 ms 178532 KB Output is correct
6 Correct 1469 ms 186836 KB Output is correct
7 Correct 1576 ms 187144 KB Output is correct
8 Correct 1610 ms 187168 KB Output is correct
9 Correct 1260 ms 183792 KB Output is correct
10 Correct 1280 ms 183928 KB Output is correct
11 Correct 1180 ms 183540 KB Output is correct
12 Correct 1235 ms 183788 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 216112 KB Output is correct
2 Correct 1151 ms 216096 KB Output is correct
3 Correct 626 ms 177452 KB Output is correct
4 Correct 587 ms 177392 KB Output is correct
5 Correct 605 ms 177432 KB Output is correct
6 Correct 903 ms 185940 KB Output is correct
7 Correct 1000 ms 185968 KB Output is correct
8 Correct 1049 ms 186104 KB Output is correct
9 Correct 876 ms 182544 KB Output is correct
10 Correct 820 ms 182484 KB Output is correct
11 Correct 926 ms 182572 KB Output is correct
12 Correct 782 ms 182600 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2887 ms 431832 KB Output is correct
2 Correct 2757 ms 431960 KB Output is correct
3 Correct 1667 ms 354680 KB Output is correct
4 Correct 1597 ms 354656 KB Output is correct
5 Correct 1686 ms 354628 KB Output is correct
6 Correct 2527 ms 371612 KB Output is correct
7 Correct 2389 ms 371648 KB Output is correct
8 Correct 2414 ms 371728 KB Output is correct
9 Correct 1837 ms 364936 KB Output is correct
10 Correct 1851 ms 364968 KB Output is correct
11 Correct 1849 ms 364956 KB Output is correct
12 Correct 1918 ms 364900 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3194 ms 432556 KB Output is correct
2 Correct 3083 ms 432516 KB Output is correct
3 Correct 1729 ms 355136 KB Output is correct
4 Correct 1879 ms 355452 KB Output is correct
5 Correct 1746 ms 355136 KB Output is correct
6 Correct 3000 ms 372372 KB Output is correct
7 Correct 2869 ms 372112 KB Output is correct
8 Correct 2877 ms 372272 KB Output is correct
9 Correct 2303 ms 365572 KB Output is correct
10 Correct 2279 ms 365472 KB Output is correct
11 Correct 2207 ms 365504 KB Output is correct
12 Correct 2273 ms 365672 KB Output is correct