Submission #492418

#	Time	Username	Problem	Language	Result	Execution time	Memory
492418		duchung	Evacuation plan (IZhO18_plan)	C++17	100 / 100	564 ms	53044 KiB

plan

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

#define ii pair<int , int>
const int N = 1e5 + 5;

int n , m , k , q;
vector<pair<int , int>> edge[N];
int dist[N] , level[N] , parent[N];
priority_queue<ii , vector<ii> , greater<ii>> pq;
set<int> S[N];
vector<ii> tmp;
int ans[N];

void dijkstra()
{
    while(!pq.empty())
    {
        int u = pq.top().second;
        int dist_u = pq.top().first;
        pq.pop();

        if (dist_u != dist[u]) continue;

        for (auto adj : edge[u])
        {
            int v = adj.first;
            int w = adj.second;

            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v] , v});
            }
        }
    }
}

int find_set(int u)
{
    return (u == parent[u] ? u : parent[u] = find_set(parent[u]));
}

void union_set(int u , int v , int w)
{
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;

    if (level[u] < level[v]) swap(u , v);
    parent[v] = u;
    if (level[u] == level[v]) ++level[u];

    if ((int) S[u].size() < (int) S[v].size()) swap(S[u] , S[v]);

    for (int x : S[v])
    {
        if (S[u].find(x) != S[u].end())
        {
            ans[x] = w;
            S[u].erase(x);
        }
        else
        {
            S[u].insert(x);
        }
    }

}

int main()
{
    // freopen(".inp","r",stdin);
    // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        int u , v , w;
        cin >> u >> v >> w;
        edge[u].push_back({v , w});
        edge[v].push_back({u , w});
    }

    for (int i = 1 ; i <= n ; ++i) dist[i] = 2e9 , parent[i] = i , level[i] = 0;

    cin >> k;
    for (int i = 1 ; i <= k ; ++i)
    {
        int u;
        cin >> u;
        pq.push({dist[u] = 0 , u});
    }

    dijkstra();

    cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        int u , v;
        cin >> u >> v;
        S[u].insert(i);
        S[v].insert(i);
    }

    // for (int i = 1 ; i <= n ; ++i) cout << dist[i] << " ";
    // cout << "\n";

    for (int i = 1 ; i <= n ; ++i) tmp.push_back({dist[i] , i});
    sort(tmp.begin() , tmp.end() , greater<ii> ());

    for (auto x : tmp)
    {
        int w = x.first , u = x.second;
        for (auto adj : edge[u])
        {
            int v = adj.first;
            if (dist[v] >= w) union_set(u , v , w);
        }
    }

    for (int i = 1 ; i <= q ; ++i) cout << ans[i] << "\n";
}

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