Submission #707052

#TimeUsernameProblemLanguageResultExecution timeMemory
707052thimote75Valley (BOI19_valley)C++14
36 / 100
3082 ms55676 KiB

#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 (delta != 0) {
        used += time_to_parent_2k[node][0];
        node  = parents_2k[node][0];

        minValue = min(minValue, used + shop_subtree[node]);
        delta --;
    }

    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);

    for (int h = 0; h + 1 < parents_2k[0].size(); h ++) {
        //printf("--- h=%d ---\n", 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];
            //printf("%d: %d\n", id, parents_2k[id][h]);
            //printf("%lld %lld\n", shop_subtree_2k[id][h], shop_subtree_2k[parents_2k[id][h]][h]);
            //printf("%lld\n", time_to_parent_2k[id][h]);
            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]
            );

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

    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 'long long int _computeShop(int, int)':
valley.cpp:80:9: warning: unused variable 'h' [-Wunused-variable]
   80 |     int h = parents_2k[0].size();
      |         ^
valley.cpp: In function 'int main()':
valley.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int h = 0; h + 1 < parents_2k[0].size(); h ++) {
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...