Submission #495349

#	Time	Username	Problem	Language	Result	Execution time	Memory
495349		kingline	Evacuation plan (IZhO18_plan)	C++17	100 / 100	770 ms	59816 KiB

plan

#include <bits/stdc++.h>
#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
#define all(data) data.begin(), data.end()
#define endl '\n'
#define ll long long
//#define int long long
#define pii pair < int, int >

using namespace std;

const int N = 1e5 + 5;
const int M = 5e5 + 5;
const int mod = 1e9 + 7;
const int lg = 21;

int n, m, k, d[N], dang[N], p[N], rk[N], a[M], b[M], up[N][lg], mn[N][lg], tin[N], tout[N], sz;
vector < pair < int, int > > g[N], gg[N];

void dijkstra() {
    for(int i = 1; i <= n; i++) {
        d[i] = mod;
    }
    set < pair < int, int > > st;
    for(int i = 1; i <= k; i++) {
        d[dang[i]] = 0;
        st.insert({0, dang[i]});
    }
    while(st.size()) {
        int now = (*st.begin()).second;
        st.erase(*st.begin());
        for(int i = 0; i < g[now].size(); i++) {
            int to = g[now][i].first, len = g[now][i].second;
            if(d[to] > d[now] + len) {
                st.erase({d[to], to});
                d[to] = d[now] + len;
                st.insert({d[to], to});
            }
        }
    }
}

int get(int x) {
    return (p[x] == x ? x : p[x] = get(p[x]));
}

void unite(int aa, int bb) {
    aa = get(aa);
    bb = get(bb);
    if(aa != bb) {
        if(rk[aa] > rk[bb]) swap(aa, bb);
        p[aa] = bb;
        rk[bb] += rk[aa];
    }
}

void dfs(int v, int pr) {
    up[v][0] = pr;
    tin[v] = ++sz;
    for(int i = 1; i < lg; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
        mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
    }
    for(int i = 0; i < gg[v].size(); i++) {
        int to = gg[v][i].first, len = gg[v][i].second;
        if(to != pr) {
            mn[to][0] = len;
            dfs(to, v);
        }
    }
    tout[v] = sz;
}

bool upper(int aa, int bb) {
    return tin[aa] <= tin[bb] && tout[aa] >= tout[bb];
}

int lca(int aa, int bb) {
    if(upper(aa, bb)) return aa;
    if(upper(bb, aa)) return bb;
    for(int i = lg - 1; i >= 0; i--) {
        if(up[aa][i] == 0) continue;
        if(!upper(up[aa][i], bb)) {
            aa = up[aa][i];
        }
    }
    return up[aa][0];
}

void solve() {
    int q, s, t; cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> s >> t;
        int res = 1e9, la = lca(s, t);
        for(int j = lg - 1; j >= 0 && la != s; j--) {
            if(up[s][j] == 0) continue;
            if(!upper(up[s][j], la)) {
                res = min(res, mn[s][j]);
                s = up[s][j];
            }
        }
        if(la != s) res = min(res, mn[s][0]);
        for(int j = lg - 1; j >= 0 && la != t; j--) {
            if(up[t][j] == 0) continue;
            if(!upper(up[t][j], la)) {
                res = min(res, mn[t][j]);
                t = up[t][j];
            }
        }
        if(la != t) res = min(res, mn[t][0]);
        cout << res << endl;
    }
}

main() {
    //file("outofplace");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int len;
        cin >> a[i] >> b[i] >> len;
        g[a[i]].pb({b[i], len});
        g[b[i]].pb({a[i], len});
    }
    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> dang[i];
    }
    dijkstra();
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        rk[i] = 1;
    }
    vector < pair < int, pii > > v;
    for(int i = 1; i <= m; i++) {
        v.pb({min(d[a[i]], d[b[i]]), {a[i], b[i]}});
    }
    sort(all(v));
    reverse(all(v));
    for(int i = 0; i < v.size(); i++) {
        int aa = get(v[i].second.first), bb = get(v[i].second.second), len = v[i].first;
        if(aa != bb) {
            unite(aa, bb);
            gg[aa].pb({bb, len});
            gg[bb].pb({aa, len});
        }
    }
    dfs(1, 1);
    solve();
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra()':
plan.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int i = 0; i < g[now].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < gg[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
plan.cpp: At global scope:
plan.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main() {
      | ^~~~
plan.cpp: In function 'int main()':
plan.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~

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