제출 #1235488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235488		Bahamin	Evacuation plan (IZhO18_plan)	C++20	100 / 100	267 ms	36728 KiB

plan

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

vector<pair<int, int>> adj[MAX_N];
int dis[MAX_N];
bool mark[MAX_N];
int n, m;

void djk()
{
    priority_queue<pair<int, int>> pq;
    fill(dis, dis + n + 1, INF);
    for (int i = 1; i <= n; i++) if (mark[i]) dis[i] = 0, pq.push(make_pair(0, i));
    while (pq.size())
    {
        auto x = pq.top();
        pq.pop();
        if (-x.first != dis[x.second]) continue;
        for (auto y : adj[x.second])
            if (dis[y.first] > -x.first + y.second) dis[y.first] = -x.first + y.second, pq.push(make_pair(-dis[y.first], y.first));
    }
}

vector<pair<int, int>> qs[MAX_N];
int sz[MAX_N];
int ans[MAX_N];
int par[MAX_N];

int getpar(int u) {return (par[u] == u ? u : par[u] = getpar(par[u]));}
void merge(int u, int v, int xx)
{
    u = getpar(u);
    v = getpar(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    for (auto x : qs[v]) 
    {
        qs[u].push_back(x);
        if (getpar(x.first) == u) ans[x.second] = xx;
    }
    par[v] = u;
    sz[u] += sz[v];
}

void solve() {
    cin >> n >> m;
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back(make_pair(u, v));
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        int x;
        cin >> x;
        mark[x] =true;
    }
    djk();
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u == v) ans[i] = dis[u];
        else qs[u].push_back(make_pair(v, i)), qs[v].push_back(make_pair(u, i)), sz[u]++, sz[v]++;
    }
    for (int i = 1; i <= n; i++) par[i] = i;
    vector<pair<int, pair<int, int>>> edges2;
    for (auto x : edges) edges2.push_back(make_pair(min(dis[x.first], dis[x.second]), x));
    sort(all(edges2), greater<pair<int, pair<int, int>>>());
    for (auto x : edges2) merge(x.second.first, x.second.second, x.first);
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}   

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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