Submission #707143

#	Time	Username	Problem	Language	Result	Execution time	Memory
707143		thimote75	Valley (BOI19_valley)	C++14	100 / 100	756 ms	62424 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define num long long
#define t_road pair<int, num>
#define idata vector<int>
#define igrid vector<idata>
#define bdata vector<bool>
#define graph vector<vector<t_road>>
#define di pair<int, int>
#define t_roads vector<di>
#define ndata vector<num>
#define ngrid vector<ndata>
#define f first
#define s second
#define LINF 1e18
#define IINF 1e9

int nbNodes, nbShops, nbQuery, root;

bdata isShop;
idata depth;
idata parents;
igrid parents_2k;
ndata shop_subtree;
ngrid shop_subtree_2k;
ngrid time_to_parent_2k;

t_roads road_array;
graph roads;

void dfs (int node, int parent, int local_depth) {
    parents   [node] = parent;
    parents_2k[node][0] = parent;
    depth[node] = local_depth;

    for (t_road next : roads[node]) {
        if (next.f != parent)
            dfs(next.f, node, local_depth + 1);
        else
            time_to_parent_2k[node][0] = next.s;
    }
}
num shop_dfs (int node, int parent) {
    shop_subtree[node] = isShop[node] ? 0 : LINF;
    
    for (t_road next : roads[node]) {
        if (next.f == parent) continue ;

        num subsubtree = shop_dfs(next.f, node) + next.s;
        shop_subtree[node] = min(shop_subtree[node], subsubtree);
    }

    shop_subtree_2k[node][0] = shop_subtree[node];
    return shop_subtree[node];
}

int warp (int node, int delta) {
    int h = parents_2k[0].size();

    while (h >= 1) {
        h --;
        if (((1 << h) & delta) == 0) continue ;

        node = parents_2k[node][h];
    }

    return node;
}
bool canEscape (int node, int subtree) {
    int depth_subtree = depth[subtree];
    int depth_node    = depth[node];

    return depth_node < depth_subtree
        || warp(node, depth_node - depth_subtree) != subtree;
}
num _computeShop (int node, int delta) {
    int h = parents_2k[0].size();
    num minValue = shop_subtree[node];
    num used = 0;

    while (h >= 1) {
        h --;
        if (((1 << h) & delta) == 0) continue ;

        minValue = min(
            minValue,
            shop_subtree_2k[node][h] + used
        );

        used += time_to_parent_2k[node][h];
        node  = parents_2k[node][h];
    }

    return minValue;
}
num computeShop (int node, int subtree) {
    int depth_subtree = depth[subtree];
    int depth_node    = depth[node];

    return _computeShop(node, depth_node - depth_subtree);
}

int main () {
    cin >> nbNodes >> nbShops >> nbQuery >> root;
    root --;
    isShop.resize(nbNodes, false);
    roads .resize(nbNodes);
    parents.resize(nbNodes);
    depth  .resize(nbNodes);
    parents_2k.resize(nbNodes, idata(ceil(log2(nbNodes))));
    shop_subtree.resize(nbNodes);
    shop_subtree_2k.resize(nbNodes, ndata(ceil(log2(nbNodes)), LINF));
    time_to_parent_2k.resize(nbNodes, ndata(ceil(log2(nbNodes)), 0));

    for (int idRoad = 1; idRoad < nbNodes; idRoad ++) {
        int a, b, w;
        cin >> a >> b >> w;
        a --; b --;

        roads[a].push_back({ b, w });
        roads[b].push_back({ a, w });
        road_array.push_back({ a, b });
    }

    for (int idShop = 0; idShop < nbShops; idShop ++) {
        int c; cin >> c; c --;

        isShop[c] = true;
    }

    dfs(root, -1, 0);
    shop_dfs(root, -1);

    // TODO compute subtree_2k which will be the min of consective 2^k (sum of length of roads to the shop)

    for (int h = 0; h + 1 < parents_2k[0].size(); h ++) {
        for (int id = 0; id < nbNodes; id ++) {
            if (parents_2k[id][h] == -1) continue ;

            parents_2k[id][h + 1] = parents_2k[parents_2k[id][h]][h];

            time_to_parent_2k[id][h + 1]
             = time_to_parent_2k[id][h] + time_to_parent_2k[parents_2k[id][h]][h];
        }
    }

    for (int id = 0; id < nbNodes; id ++) {
        if (parents_2k[id][0] == -1) continue ;

        shop_subtree_2k[id][0]
         = min(shop_subtree[id], shop_subtree[parents_2k[id][0]] + time_to_parent_2k[id][0]);
        //printf("%d %d: %lld\n", 0, id, shop_subtree_2k[id][0]);
    }

    for (int h = 0; h + 1 < parents_2k[0].size(); h ++) {
        for (int id = 0; id < nbNodes; id ++) {
            if (parents_2k[id][h] == -1) continue ;

            shop_subtree_2k[id][h + 1]
            = min(
                shop_subtree_2k[id][h],
                shop_subtree_2k[parents_2k[id][h]][h]
              + time_to_parent_2k[id][h]
            );
            //printf("%d %d: %lld\n", h + 1, id, shop_subtree_2k[id][h + 1]);
        }
    }

    for (int idQuery = 0; idQuery < nbQuery; idQuery ++) {
        int a, road;
        cin >> road >> a;
        a --; road --;

        di r_road = road_array[road];
        int bottom = depth[r_road.f] > depth[r_road.s] ? r_road.f : r_road.s;

        if (canEscape(a, bottom)) {
            cout << "escaped\n";
            continue ;
        }

        num answer = computeShop(a, bottom);
        if (answer == LINF) cout << "oo\n";
        else cout << answer << endl;
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:139:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int h = 0; h + 1 < parents_2k[0].size(); h ++) {
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:158:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int h = 0; h + 1 < parents_2k[0].size(); h ++) {
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41