Submission #720817

#	Time	Username	Problem	Language	Result	Execution time	Memory
720817		thimote75	Evacuation plan (IZhO18_plan)	C++14	100 / 100	999 ms	44656 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define bdata vector<bool>
#define idata vector<int>
#define graph vector<idata>
#define t_road pair<int, int>
#define rnext first
#define rcost second
#define t_roads vector<t_road>
#define w_graph vector<t_roads>
#define inf 1e9
#define di pair<int, int>
#define pq_dist set<di>
#define igrid vector<idata>

struct SegTree {
    idata tree;
    int size, start, height;

    void init (idata &res) {
        size = res.size();
        height = ceil(log2(size));
        start = 1 << height;

        tree.resize(start << 1, inf);
        for (int i = 0; i < size; i ++)
            tree[i + start] = res[i];
        
        for (int i = start - 1; i >= 1; i --)
            tree[i] = min(tree[2 * i], tree[2 * i + 1]);
    }
    int query (int l, int r) {
        l += start; r += start;
        int res = inf;

        while (l < r) {
            if ((l & 1) == 1) res = min(res, tree[l]);
            if ((r & 1) == 0) res = min(res, tree[r]);
        
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) res = min(res, tree[l]);

        return res;
    }
};

int nbNodes, nbRoads, nbNPP, nbQuery;
graph roads;
w_graph w_roads;

idata dist_npp;

idata dijkstra ( idata &start ) {
    idata res(nbNodes, inf);
    pq_dist node_queue;

    for (int u : start) {
        res[u] = 0;
        node_queue.insert({ 0, u });
    }

    while (node_queue.size() != 0) {
        di current = *(node_queue.begin());
        node_queue.erase(current);

        int dist = current.first;
        int node = current.second;
        if (dist != res[node]) continue ;

        for (t_road road : w_roads[node]) if (res[road.rnext] > dist + road.rcost) {
            di old = { res[road.rnext], road.rnext };
            
            res[road.rnext] = dist + road.rcost;
            node_queue.insert({ res[road.rnext], road.rnext });
        }
    }

    return res;
}

idata ufd_boss;
int boss (int x) {
    if (ufd_boss[x] != x)
        ufd_boss[x] = boss(ufd_boss[x]);
    return ufd_boss[x];
}
void compute_residual () {
    ufd_boss.resize(nbNodes);
    for (int i = 0; i < nbNodes; i ++)
        ufd_boss[i] = i;

    bdata visited(nbNodes);
    priority_queue<pair<pair<int, int>, pair<int, int>>> pq;

    for (int iN = 0; iN < nbNodes; iN ++) {
        for (t_road road : w_roads[iN]) {
            if (dist_npp[iN] < dist_npp[road.rnext]
             ||(dist_npp[iN] == dist_npp[road.rnext] && iN < road.rnext)) {
                pq.push({
                    { dist_npp[iN], dist_npp[road.rnext] },
                    { iN, road.rnext }
                });
            }
        }
    }

    while (pq.size() != 0) {
        auto mu = pq.top(); pq.pop();

        int a = mu.second.first;
        int b = mu.second.second;

        if (boss(a) == boss(b)) continue ;
        ufd_boss[boss(a)] = boss(b);

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

const int MAX_N = 1e5 + 10;
const int MAX_K = 20;

idata depth;
idata parents;
idata subtree_size;
igrid parents_2k;

int dfs (int node, int parent, int l_depth) {
    depth       [node]    = l_depth;
    parents     [node]    = parent;
    parents_2k  [node][0] = parent;
    subtree_size[node]    = 1;

    for (int next : roads[node]) if (next != parent)
        subtree_size[node] += dfs(next, node, l_depth + 1);

    return subtree_size[node];
}

idata branch_main;
idata segtree_pos;
idata segtree_val;
int segtree_used = 0;
int idBranch = 0;
SegTree tree;
void create_branch (int node, int parent);
void hld (int node, int parent, int branch) {
    segtree_pos[node] = segtree_used ++;
    branch_main[node] = branch;

    segtree_val[segtree_pos[node]] = dist_npp[node];

    int mxSubtree = -1;
    int mxSubNode = -1;

    for (int next : roads[node]) if (next != parent && subtree_size[next] > mxSubtree) {
        mxSubtree = subtree_size[next];
        mxSubNode = next;
    }

    if (mxSubNode != -1)
        hld(mxSubNode, node, branch);

    for (int next : roads[node]) if (next != parent && next != mxSubNode)
        create_branch(next, node);
}
void create_branch (int node, int parent) {
    hld(node, parent, node);
}

int jump (int n, int k) {
    for (int i = 0; i < MAX_K; i ++) {
        if (((1 << i) & k) != 0) {
            n = parents_2k[n][i];
        }
    }

    return n;
}
int lca (int a, int b) {
    if (depth[a] > depth[b]) return lca(b, a);

    b = jump(b, depth[b] - depth[a]);
    if (a == b) return a;
    
    for (int i = MAX_K - 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];
}
int _compute_min( int node, int parent, int _depth = 0 ) {
    if (branch_main[node] == branch_main[parent])
        return tree.query( segtree_pos[parent], segtree_pos[node] );
    
    int next = parents[branch_main[node]];
    int quer = branch_main[node];

    return min(
        _compute_min(next, parent, _depth + 1),
        tree.query( segtree_pos[quer], segtree_pos[node] )
    );
}
int compute_min (int a, int b) {
    int l = lca(a, b);

    return min( _compute_min(a, l), _compute_min(b, l) );
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> nbNodes >> nbRoads;
    w_roads.resize(nbNodes);
    roads  .resize(nbNodes);
    parents_2k.resize(nbNodes, idata(MAX_K));

    for (int iR = 0; iR < nbRoads; iR ++) {
        int a, b, c;
        cin >> a >> b >> c;

        a --;
        b --;
        w_roads[a].push_back({ b, c });
        w_roads[b].push_back({ a, c });
    }

    cin >> nbNPP;
    idata NPP_array(nbNPP);
    for (int iP = 0; iP < nbNPP; iP ++) {
        cin >> NPP_array[iP];
        NPP_array[iP] --;
    }
    
    dist_npp = dijkstra(NPP_array);
    compute_residual();

    depth  .resize(nbNodes);
    parents.resize(nbNodes);

    subtree_size.resize(nbNodes);

    for (int k = 0; k < MAX_K; k ++)
        for (int i = 0; i < nbNodes; i ++)
            parents_2k[i][k] = -1;
    
    dfs(0, -1, 0);

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

            parents_2k[i][k + 1] = parents_2k[parents_2k[i][k]][k];
        }
    }

    segtree_pos.resize(nbNodes);
    branch_main.resize(nbNodes);
    segtree_val.resize(nbNodes);
    create_branch(0, -1);

    tree.init(segtree_val);

    cin >> nbQuery;
    for (int iQ = 0; iQ < nbQuery; iQ ++) {
        int s, t;
        cin >> s >> t;
        s --; t --;

        cout << compute_min(s, t) << endl;
    }
}

Compilation message (stderr)

plan.cpp: In function 'std::vector<int> dijkstra(std::vector<int>&)':
plan.cpp:77:16: warning: variable 'old' set but not used [-Wunused-but-set-variable]
   77 |             di old = { res[road.rnext], road.rnext };
      |                ^~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46