Submission #118011

#	Time	Username	Problem	Language	Result	Execution time	Memory
118011		DystoriaX	Evacuation plan (IZhO18_plan)	C++14	19 / 100	778 ms	46424 KiB

plan

#include <bits/stdc++.h>

using namespace std;

int n, m, q, k;
int par[100010];
int dist[100010];
vector<pair<int, int> > adj[100010];
vector<tuple<int, int, int> > edges;
bitset<100010> vis;
priority_queue<pair<int, int> > pq;
const int lgmx = log2(100000) + 2;
int sp[lgmx][100010], cost[lgmx][100010], d[100010];

void init(){
    for(int i = 1; i <= n; i++) par[i] = i;
}

int findR(int x){
    return par[x] == x ? x : par[x] = findR(par[x]);
}

void join(int a, int b){
    par[findR(a)] = findR(b);
}

void dfs(int u, int p){
    for(int i = 1; i < lgmx; i++)
        if(sp[i - 1][u] != -1) sp[i][u] = sp[i - 1][sp[i - 1][u]], cost[i][u] = min(cost[i - 1][u], cost[i - 1][sp[i - 1][u]]);

    for(auto k : adj[u]){
        int v = k.first;
        if(v == p) continue;

        d[v] = d[u] + 1;
        sp[0][v] = u;
        cost[0][v] = min(dist[u], dist[v]);

        dfs(v, u);
    }
}

int get(int u, int v){
    int c = 1e9;

    if(d[u] < d[v]) swap(u, v);

    int diff = d[u] - d[v];

    for(int i = 0; i < lgmx; i++){
        if(diff & (1 << i)) c = min(c, cost[i][u]), u = sp[i][u];
    }

    if(u == v) return c;

    for(int i = lgmx - 1; i >= 0; i--){
        if(sp[i][u] != sp[i][v]){
            c = min(c, min(cost[i][u], cost[i][v]));
            u = sp[i][u], v = sp[i][v];
        }
    }

    return min(c, cost[0][u]);
}

int main(){
    scanf("%d%d", &n, &m);

    while(m--){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    for(int i = 1; i <= n; i++) dist[i] = 1e9;

    scanf("%d", &k);
    while(k--){
        int x; scanf("%d", &x);
        pq.push({0, x});
        dist[x] = 0;
    }

    //Dijkstra
    while(!pq.empty()){
        int u, w;
        tie(w, u) = pq.top(); pq.pop(); w = -w;

        if(vis[u]) continue;
        vis[u] = 1;

        for(auto k : adj[u]){
            int v, w; tie(v, w) = k;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }

    for(int u = 1; u <= n; u++){
        for(auto k : adj[u]) edges.emplace_back(min(dist[u], dist[k.first]), u, k.first);
        adj[u].clear();
    }

    sort(edges.rbegin(), edges.rend());

    init();
    for(auto k : edges){
        int u, v, w;
        tie(w, u, v) = k;

        if(findR(u) == findR(v)) continue;
        join(u, v);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    for(int i = 1; i <= n; i++)
        for(int j = 0; j < lgmx; j++)
            cost[j][i] = 1e9;

    memset(sp, -1, sizeof(sp));
    dfs(1, -1);

    scanf("%d", &q);

    while(q--){
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", get(u, v));
    }
    
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:80:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x);
                ~~~~~^~~~~~~~~~
plan.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
plan.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

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