Submission #1093972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093972		ToTenLinh	Evacuation plan (IZhO18_plan)	C++17	100 / 100	522 ms	63908 KiB

plan

#include <bits/stdc++.h>
#define fo(i,m,n) for(int i=m;i<=n;i++)
#define fod(i,n,m) for(int i=n;i>=m;i--)
#define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k)
#define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k)
#define fol(i,m,n) for(long long i=m;i<=n;i++)
#define fodl(i,n,m) for(long long i=n;i>=m;i--)
#define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k)
#define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k)
#define lb lower_bound
#define ub upper_bound
#define pii pair <int,int>
#define vii vector<pii>
#define fi first
#define se second
#define si size()
#define pb push_back
#define ppb pop_back()
#define fr front()
#define et empty()
#define bg begin()
#define ub upper_bound
#define lb lower_bound
#define ed end()
#define el endl
#define EL cout << '\n';
using namespace std;
using ll = long long ;
#define int ll
const int mod = 1e9 + 7;
const int N = 1e5 + 69;
const int M = 1e3 + 5;
template<class T> constexpr T inf = ::numeric_limits<T>::max() / 32 * 15 + 208;
int n, m, k, q, city[N] ;
ll dist[N] ;
ll a[N] ;
vector<pair<ll,int>> g[N];
vector<int> adj[N] ;

void djickstra()
{
    for (int i = 1 ; i <= n ; i++)
    {
        dist[i] = inf<ll> ;
    }
    set<pair<ll,int>> st;
    for (int i = 0 ; i < k ; i++)
    {
        st.insert({0, city[i]}) ;
        dist[city[i]] = 0 ;
    }
    while (st.size())
    {
        auto [val, v] = *st.begin() ;
        st.erase(st.begin()) ;
        for (auto [w, to] : g[v])
        {
            if (dist[to] > dist[v] + w)
            {
                st.erase({dist[to], to}) ;
                dist[to] = dist[v] + w ;
                st.insert({dist[to], to}) ;
            }
        }
    }
}

struct DSU
{
    vector<int> parent, sz ;
    DSU(int n)
    {
        parent.resize(n) ;
        iota(begin(parent), end(parent), 0) ;
        sz.assign(n, 1) ;
    }
    int find(int i)
    {
        if (i == parent[i])
        {
            return i ;
        }
        else
        {
            return parent[i] = find(parent[i]) ;
        }
    }
    bool unite(int u, int v)
    {
        u = find(u), v = find(v) ;
        if (u == v) return false ;
        if (sz[v] == sz[u]) sz[v]++ ;
        if (sz[v] < sz[u]) swap(u, v) ;
        parent[u] = v ;
        return true ;
    }
    bool same(int u, int v)
    {
        return (find(u) == find(v)) ;
    }
};

int chain[N], sz[N] ;
int tin[N], timer, t[N * 4], c[N], pr[N], depth[N] ;

void dfs(int v, int p)
{
    pr[v] = p ;
    sz[v] = 1 ;
    for (auto to : adj[v])
    {
        if (to != p)
        {
            depth[to] = depth[v] + 1 ;
            dfs(to, v) ;
            sz[v] += sz[to] ;
        }
    }
}

void hld(int v, int p, int head)
{
    tin[v] = ++timer ;
    chain[v] = head ;
    int cur = 0 ;
    for (auto to : adj[v])
    {
        if (to != p && sz[to] > sz[cur]) cur = to ;
    }
    if (cur)
    {
        hld(cur, v, head) ;
    }
    for (auto to : adj[v])
    {
        if (to == p || to == cur)
        {
            continue ;
        }
        hld(to, v, to) ;
    }
}

void upd(int i, int x, int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] = x ;
    }
    else
    {
        int tm = (tl + tr) / 2;
        if (i <= tm)
        {
            upd(i, x, v * 2, tl, tm) ;
        }
        else
        {
            upd(i, x, v * 2 + 1, tm + 1, tr) ;
        }
        t[v] = min(t[v * 2], t[v * 2 + 1]) ;
    }
}

int get(int l, int r, int v, int tl, int tr)
{
    if (l > r) swap(l, r) ;
    if (l > tr || r < tl) return inf<ll> ;
    if (l <= tl && tr <= r) return t[v] ;
    int tm = (tl + tr) / 2;
    return min(get(l,r,v*2,tl,tm), get(l,r,v*2+1,tm+1,tr)) ;
}

int query(int u, int v)
{
    int ans = inf<ll> ;
    while (chain[u] != chain[v])
    {
        if (depth[chain[u]] < depth[chain[v]]) swap(u, v) ;
        int boss = chain[u] ;
        if (u == boss)
        {
            ans = min(ans, a[u]) ;
            u = pr[u] ;
        }
        else
        {
            ans = min(ans, get(tin[u], tin[boss], 1, 1, n)) ;
            u = pr[boss] ;
        }
    }
    int l = tin[u], r = tin[v] ;
    ans = min(ans, get(l,r,1,1,n)) ;
    return ans ;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(false) ;
    cin >> n >> m;
    vector<tuple<ll,ll,ll>> edge(m) ;
    for (int i = 0 ; i < m ; i++)
    {
        ll u, v, w ;
        cin >> u >> v >> w ;
        g[u].push_back({w, v}) ;
        g[v].push_back({w, u}) ;
        edge[i] = {0, u, v} ;
    }
    cin >> k;
    for (int i = 0 ; i < k ; i++)
    {
        cin >> city[i] ;
    }

    djickstra() ;
    for (int i = 0 ; i < m ; i++)
    {
        auto& [val, u, v] = edge[i] ;
        val = min(dist[u], dist[v]) ;
    }
    sort(edge.rbegin(), edge.rend()) ;
    int ptr = -1 ;
    DSU d(n + 1) ;
    for (auto [val, u, v] : edge)
    {
        if (d.unite(u, v))
        {
            adj[u].push_back(v) ;
            adj[v].push_back(u);
        }
    }
    dfs(1, 0) ;
    hld(1, 0, 1) ;
    for (int i = 1 ; i <=n ; i++)
    {
        a[i] = dist[i] ;
    }
    for (int i = 1 ; i <= n ; i++)
    {
        upd(tin[i], a[i], 1, 1, n) ;
    }
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        cout << query(u, v) << "\n" ;
    }
    return 0 ;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:222:9: warning: unused variable 'ptr' [-Wunused-variable]
  222 |     int ptr = -1 ;
      |         ^~~

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