Submission #94218

#	Time	Username	Problem	Language	Result	Execution time	Memory
94218		4llower	Evacuation plan (IZhO18_plan)	C++14	0 / 100	887 ms	110232 KiB

plan

#include <bits/stdc++.h>

#define rust(a, b, c, d) sqrt(sqr(a - c) + sqr(b - d))
#define sqr(a) (a)*(a)
#define m_p make_pair
#define fi first
#define se second
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define pll pair <ll,ll>
#define next stopplz
#define y1 STOPPLZ

typedef long long ll;

const int MAXINT=2147483640;
const ll MAXLL=9223372036854775800LL;
const ll MAXN = 1e6;
const double eps = 1e-9;
const ll mod = 1e9 + 7;

using namespace std;
ll dsu[MAXN], tin[MAXN], tout[MAXN], p[100020][22], ans[100200][22], n, m, b[MAXN], stn, v1[MAXN], v2[MAXN];
vector <pll> v[MAXN];
ll get(ll x){
    if (dsu[x] != x) dsu[x] = get(dsu[x]);
    return dsu[x];
}
void dfs(ll x, ll pred){
    p[x][0] = pred;
    ans[x][0] = b[pred];
    tin[x] = ++stn;
    for (int i = 1; i <= 20; ++i) {
            p[x][i] = max(1ll, p[p[x][i - 1]][i - 1]);
            ans[x][i] = min(ans[x][i - 1], ans[p[x][i - 1]][i - 1]);
    }
    for (auto i : v[x]) if (i.fi != pred) dfs(i.fi, x);
    tout[x] = ++stn;
}

bool lower(ll x, ll y){
    if (tin[x] <= tin[y] && tout[y] <= tout[x]) return 1;
    else return 0;
}

ll lca(ll x, ll y){
    if (lower(x, y)) return 1e18;
    ll val = 1e18;
    for (int i = 20; i >= 0; i--) if (!lower(p[x][i], y)) {
            val = min(val, ans[x][i]);
            x = p[x][i];
    }
    val = min(val, ans[p[x][0]][0]);
    return val;
}

int main() {
    srand(time(0));
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    fast_io;
    cin >> n >> m;
    for (int i = 0; i <= n; ++i) dsu[i] = i, b[i] = 1e18;
    vector <pair <ll, pll> > vans;
    for (int i = 1; i <= m; ++i){
        ll val;
        cin >> v1[i] >> v2[i] >> val;
        v[v1[i]].push_back(m_p(v2[i], val));
        v[v2[i]].push_back(m_p(v1[i], val));
    }

    ll k;
    cin >> k;
    set <pll> s;
    for (int i = 1; i <= k; ++i) {
        ll x;
        cin >> x;
        s.insert(m_p(0, x));
        b[x] = 0;
    }

    while (!s.empty()){
        ll x = s.begin() -> se, val = s.begin() -> fi;
        s.erase(s.begin());
        for (auto i : v[x]) if (val + i.se < b[i.fi]){
            s.erase(m_p(b[i.fi], i.fi));
            b[i.fi] = i.se + val;
            s.insert(m_p(b[i.fi], i.fi));
        }
    }

    for (int i = 1; i <= n; ++i) v[i].clear();
    for (int i = 1; i <= m; ++i) vans.push_back(m_p(min(b[v1[i]], b[v2[i]]), m_p(v1[i], v2[i])));
    sort(vans.begin(), vans.end());
    reverse(vans.begin(), vans.end());
    for (auto i : vans) if (get(i.se.se) != get(i.se.fi)){
        dsu[get(i.se.se)] = get(i.se.fi);
        v[i.se.se].push_back(m_p(i.se.fi, 0));
        v[i.se.fi].push_back(m_p(i.se.se, 0));
    }

    dfs(1, 0);

    ll kek;
    cin >> kek;
    for (int i = 1; i <= kek; ++i){
        ll l, r;
        cin >> l >> r;
        ll mn = lca(l, r);
        mn = min(lca(r, l), mn);
        mn = min(b[l], mn);
        mn = min(b[r], mn);
        cout << mn << endl;
    }

    return 0;
}

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