Submission #1128659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128659		Zero_OP	Evacuation plan (IZhO18_plan)	C++20	100 / 100	493 ms	42032 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 1e5 + 5;

int lab[MAX];

int root(int u){
    return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}

bool join(int u, int v){
    u = root(u);
    v = root(v);
    if(u == v) return false;
    if(lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
}

int N, M, Q, K, d[MAX];
vector<pair<int, int>> adj[MAX];
vector<pair<int, int>> adj_tree[MAX];

int depth[MAX], lift[20][MAX], upmin[20][MAX];

void dfs(int u, int p){
    for(auto [v, w] : adj_tree[u]) if(v != p){
        depth[v] = depth[u] + 1;
        lift[0][v] = u;
        upmin[0][v] = w;
        for(int i = 1; (1 << i) <= depth[v]; ++i){
            lift[i][v] = lift[i - 1][lift[i - 1][v]];
            upmin[i][v] = min(upmin[i - 1][v], upmin[i - 1][lift[i - 1][v]]);
        }
        dfs(v, u);
    }
}

int get_min(int u, int v){
    int cur = INT_MAX;
    if(depth[u] < depth[v]) swap(u, v);
    for(int i = 16; i >= 0; --i) if(depth[u] - (1 << i) >= depth[v]){
        cur = min(cur, upmin[i][u]);
        u = lift[i][u];
    }

    if(u == v) return cur;
    for(int i = 16; i >= 0; --i){
        if(lift[i][u] != lift[i][v]){
            cur = min(cur, min(upmin[i][u], upmin[i][v]));
            u = lift[i][u];
            v = lift[i][v];
        }
    }
    return min(cur, min(upmin[0][u], upmin[0][v]));
}

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

    file("A");

    cin >> N >> M;
    while(M--){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    memset(d, -1, sizeof(d));

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    cin >> K;
    for(int i = 0; i < K; ++i){
        int u;
        cin >> u;
        d[u] = 0;
        pq.push({0, u});
    }

    while(!pq.empty()){
        int cur, u;
        tie(cur, u) = pq.top(); pq.pop();
        if(d[u] != cur) continue;
        for(auto [v, w] : adj[u]){
            if(d[v] == -1 || d[v] > d[u] + w){
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }

    vector<tuple<int, int, int>> edges;
    for(int i = 1; i <= N; ++i){
        for(auto [j, w] : adj[i]){
            w = min(d[i], d[j]);
            edges.emplace_back(w, i, j);
        }
    }

    sort(all(edges));
    reverse(all(edges));

    memset(lab, -1, sizeof(lab));
    for(auto [w, u, v] : edges){
        if(join(u, v)){
            adj_tree[u].emplace_back(v, w);
            adj_tree[v].emplace_back(u, w);
        }
    }

    dfs(1, -1);

    cin >> Q;
    while(Q--){
        int s, t;
        cin >> s >> t;
        cout << get_min(s, t) << '\n';
    }

    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:10:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:96:5: note: in expansion of macro 'file'
   96 |     file("A");
      |     ^~~~
plan.cpp:10:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:96:5: note: in expansion of macro 'file'
   96 |     file("A");
      |     ^~~~

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