Submission #1173147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173147		AtabayRajabli	Evacuation plan (IZhO18_plan)	C++20	100 / 100	316 ms	55776 KiB

plan

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;

const int sz = 5e5 + 1, inf = INT_MAX;
int n, m, qs, k, cnt, in[sz], out[sz], d[sz], u[sz], v[sz], w[sz], p[sz], dp[17][sz], mn[17][sz];
vector<array<int, 2>> g[sz];

int par(int x)
{
    if(p[x] < 0) return x;
    return p[x] = par(p[x]);
}

bool join(int u, int v)
{
    u = par(u), v = par(v);
    if(u == v) return 0;
    if(p[u] > p[v]) swap(u, v);
    p[u] += p[v];
    p[v] = u;
    return 1;
}

void dfs(int v, int p)
{
    dp[0][v] = p;
    in[v] = ++cnt;
    for(auto i : g[v])
    {
        int u = i[0], w = i[1];
        if(u == p) continue;
        d[u] = d[v] + 1;
        mn[0][u] = w;
        dfs(u, v);
    }
    out[v] = cnt;
}

bool anc(int x, int y)
{
    return in[x] <= in[y] && out[y] <= out[x];
}

int lca(int u, int v)
{
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    for(int i = 16; i >= 0; i--)
    {
        if(!anc(dp[i][u], v)) u = dp[i][u];
    }
    return dp[0][u];
}

int get(int u, int v)
{
    int cm = lca(u, v);
    int du = d[u] - d[cm];
    int dv = d[v] - d[cm];
    int res = inf;
    for(int i = 0; i < 17; i++)
    {
        if((1 << i) & du)
        {
            res = min(res, mn[i][u]);
            u = dp[i][u];
        }
    }
    for(int i = 0; i < 17; i++)
    {
        if((1 << i) & dv)
        {
            res = min(res, mn[i][v]);
            v = dp[i][v];
        }
    }
    return res;
}

void solve()
{
    out[0] = inf;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        g[u[i]].push_back({v[i], w[i]});
        g[v[i]].push_back({u[i], w[i]});
    }
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> q;
    fill(d + 1, d + 1 + n, inf);
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int npp;
        cin >> npp;
        q.push({0, npp});
        d[npp] = 0;
    }
    while(!q.empty())
    {
        int v = q.top()[1], dist = q.top()[0];
        q.pop();
        if(dist > d[v]) continue;
        for(auto i : g[v])
        {
            int u = i[0], w = i[1];
            if(d[u] > d[v] + w)
            {
                d[u] = d[v] + w;
                q.push({d[u], u});
            }
        }
    }
    vector<array<int, 3>> e;
    for(int i = 1; i <= m; i++)
    {
        w[i] = min(d[u[i]], d[v[i]]);
        e.push_back({w[i], u[i], v[i]});
    }
    sort(all(e), greater<array<int, 3>>());
    fill(p + 1, p + 1 + n, -1);
    for(int i = 1; i <= n; i++) g[i].clear(), d[i] = 0;
    for(auto ex : e)
    {
        if(join(ex[1], ex[2]))
        {
            g[ex[1]].push_back({ex[2], ex[0]});
            g[ex[2]].push_back({ex[1], ex[0]});
        }
    }
    dfs(1, 1);
    for(int i = 1; i < 17; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][dp[i - 1][j]]);
        }
    }
    cin >> qs;
    while(qs--)
    {
        int s, t;
        cin >> s >> t;
        cout << get(s, t) << '\n';
    }
}

signed main()
{                                                                  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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