Submission #823667

#	Time	Username	Problem	Language	Result	Execution time	Memory
823667		thimote75	Tourism (JOI23_tourism)	C++14	28 / 100	5086 ms	46112 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using iset  = set<int>;
using igrid = vector<idata>;

using di = pair<int, int>;
using vd = vector<di>;

const int MAXK = 20;

struct Tree {
    igrid roads;

    idata preordre, postordre, parents, depth;
    igrid eulertour;
    igrid parents_2k;

    void dfs (int node, int parent, int _depth, int &iOrdre) {
        preordre[node] = iOrdre ++;
        parents [node] = parent;
        depth   [node] = _depth;

        for (int next : roads[node]) if (next != parent) {
            eulertour[node].push_back(iOrdre ++);
            dfs(next, node, _depth + 1, iOrdre);
        }
        
        postordre[node] = iOrdre ++;
    }

    Tree (int N, igrid &roads) : roads(roads) {
        eulertour.resize(N);
        postordre.resize(N);
        preordre .resize(N);
        parents  .resize(N);
        depth    .resize(N);

        int iOrdre = 0;
        dfs (0, -1, 0, iOrdre);

        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];
            }
        }
    }

    int jump (int node, int k) {
        for (int i = 0; i < MAXK; i ++)
            if ((1 << i) & k)
                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];
        }

        if (a == b) return a;
        return parents[a];
    }
};

struct VirtualTree {
    int size = 1;
    map<int, int> id_to_vid;

    VirtualTree (Tree &tree, iset virtual_set) {
        vd order_positions;
        for (int u : virtual_set) order_positions.push_back({ tree.preordre[u], u });

        sort(order_positions.begin(), order_positions.end());

        for (int i = 0; i + 1 < order_positions.size(); i ++){
            int u = order_positions[i    ].second;
            int v = order_positions[i + 1].second;

            int l = tree.lca(u, v);
            virtual_set.insert(l);
        }

        vd dist_computations;
        for (int u : virtual_set) {
            dist_computations.push_back({ tree.preordre [u], u }); 
            for (int h : tree.eulertour[u])
                dist_computations.push_back({ h, u });
            dist_computations.push_back({ tree.postordre[u], u }); 
        }

        sort(dist_computations.begin(), dist_computations.end());

        set<pair<int, int>> pot_roads;

        for (int i = 0; i + 1 < dist_computations.size(); i ++) {
            int u = dist_computations[i]    .second;
            int v = dist_computations[i + 1].second;

            if (u == v) continue ;
            pot_roads.insert({ min(u, v), max(u, v) });
        }

        int iNode = 0;
        for (int u : virtual_set)
            id_to_vid.insert({ u, iNode ++ });
        
        for (const auto &road : pot_roads) {
            int u = road.first; int v = road.second;
            int dist = abs(tree.depth[u] - tree.depth[v]);

            size += dist;
        }
    }
};

int main () {
    int N, M, Q;
    cin >> N >> M >> Q;

    igrid roads(N);
    for (int i = 1; i < N; i ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        roads[a].push_back(b);
        roads[b].push_back(a);
    }

    Tree tree(N, roads);

    idata R(M);
    for (int i = 0; i < M; i ++) {
        cin >> R[i];
        R[i] --;
    }
    
    for (int q = 0; q < Q; q ++) {
        int l, r;
        cin >> l >> r;
        l --; r --;

        iset SV;
        for (int u = l; u <= r; u ++) SV.insert(R[u]);

        VirtualTree vTree(tree, SV);
        cout << vTree.size << "\n";
    }
}

Compilation message (stderr)

tourism.cpp: In constructor 'VirtualTree::VirtualTree(Tree&, iset)':
tourism.cpp:93:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int i = 0; i + 1 < order_positions.size(); i ++){
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:113:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for (int i = 0; i + 1 < dist_computations.size(); i ++) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41