제출 #981449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981449		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	415 ms	103628 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 1e6+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n,m,k,q, d[SZ], a[SZ];

struct Node
{
    int u,d;

    bool operator < (const Node& other) const
    {
        return d > other.d;
    }
};
priority_queue<Node> pq;
vector<pii> adj[SZ];

void dijkstra()
{
    while(!pq.empty())
    {
        int u = pq.top().u, dist = pq.top().d;
        pq.pop();
        if(d[u] < dist) continue;
        for(pii e : adj[u])
        {
            int v = e.fi, w = e.se;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                pq.push({v, d[v]});
            }
        }
    }
}

bool cmp(int x, int y)
{
    return d[x] > d[y];
}

struct DSU
{
    int s[SZ], par[SZ];

    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            s[i] = 1;
            par[i] = i;
        }
    }

    int get(int u)
    {
        return par[u] == u ? u : par[u] = get(par[u]);
    }

    void join(int u, int v)
    {
        if(s[u] < s[v]) swap(u, v);
        s[u] += s[v];
        par[v] = u;
    }
} dsu;

bool check[SZ];
vector<int> mst[SZ];
int h[SZ], up[SZ][20], val[SZ][20];

void dfs(int u, int pre)
{
    for(int v : mst[u])
    {
        if(v == pre) continue;
        h[v] = h[u] + 1;
        val[v][0] = d[u];
        up[v][0] = u;
        for(int i = 1; i < 20; i++)
        {
            up[v][i] = up[up[v][i-1]][i-1];
            val[v][i] = min(val[v][i-1], val[up[v][i-1]][i-1]);
        }
        dfs(v, u);
    }
}

int res(int u, int v)
{
    int mn = min(d[u], d[v]);
    if(h[u] != h[v])
    {
        if(h[u] < h[v]) swap(u, v);
        int diff = h[u] - h[v];
        for(int i = 0; i < 20; i++)
        {
            if(diff >> i & 1)
            {
                mn = min(mn, val[u][i]);
                u = up[u][i];
            }
        }
    }
    if(u == v) return mn;
    for(int i = 19; i >= 0; i--)
    {
        if(up[u][i] != up[v][i])
        {
            mn = min({mn, val[u][i], val[v][i]});
            u = up[u][i];
            v = up[v][i];
        }
    }
    return min(mn, d[up[u][0]]);
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    for(int i = 1; i <= n; i++)
    {
        d[i] = INF;
        a[i] = i;
    }
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int u;
        cin >> u;
        pq.push({u, 0});
        d[u] = 0;
    }
    dijkstra();
    sort(a + 1, a + n + 1, cmp);
    dsu.init(n);
    for(int i = 1; i <= n; i++)
    {
        int u = a[i];
        check[u] = true;
        for(pii e : adj[u])
        {
            int v = e.fi, w = e.se;
            int x = dsu.get(u), y = dsu.get(v);
            if(!check[v] || x == y) continue;
            dsu.join(x, y);
            mst[u].pb(v);
            mst[v].pb(u);
        }
    }
    dfs(1, 0);
    cin >> q;
    while(q--)
    {
        int u,v;
        cin >> u >> v;
        cout << res(u, v) << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int main()':
plan.cpp:175:27: warning: unused variable 'w' [-Wunused-variable]
  175 |             int v = e.fi, w = e.se;
      |                           ^

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