Submission #883136

#	Time	Username	Problem	Language	Result	Execution time	Memory
883136		boris_mihov	Evacuation plan (IZhO18_plan)	C++17	100 / 100	340 ms	61832 KiB

plan

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <vector>
#include <bitset>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 500000 + 10;
const int INF  = 1e9;

int n, m, k, q;
int answer[MAXN];

struct DSU
{
    struct Query
    {
        int u, v;
        int idx;
    };

    int par[MAXN];
    std::vector <Query> queries[MAXN];

    void build()
    {
        std::iota(par + 1, par + 1 + n, 1);
    }

    int find(int node)
    {
        if (par[node] == node) return node;
        return par[node] = find(par[node]);
    }

    void connect(int u, int v, int newMin)
    {
        u = find(u);
        v = find(v);

        if (u == v)
        {
            return;
        }

        if (queries[u].size() < queries[v].size())
        {
            std::swap(u, v);
        }

        par[v] = u;
        for (const Query &curr : queries[v])
        {
            if (areConnected(curr.v, curr.u))
            {
                if (answer[curr.idx] == -1) answer[curr.idx] = newMin;
            } else
            {
                queries[u].push_back(curr);
            }
        }
    }

    bool areConnected(int u, int v)
    {
        return find(u) == find(v);
    }
};

DSU dsu;
int dist[MAXN];
int perm[MAXN];
std::vector <int> npp;
std::priority_queue <std::pair <int,int>> pq;
std::vector <std::pair <int,int>> g[MAXN];
bool vis[MAXN];

void solve()
{
    std::fill(dist + 1, dist + 1 + n, INF);
    for (int i = 0 ; i < k ; ++i)
    {
        dist[npp[i]] = 0;
        pq.push({0, npp[i]});
    }

    while (!pq.empty())
    {
        auto [d, node] = pq.top();
        pq.pop();

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, w] : g[node])
        {
            if (dist[u] > dist[node] + w)
            {
                dist[u] = dist[node] + w;
                pq.push({-dist[u], u});
            }
        }
    }

    std::cin >> q;
    dsu.build();

    std::fill(answer + 1, answer + 1 + q, -1);
    for (int i = 1 ; i <= q ; ++i)
    {
        int from, to;
        std::cin >> from >> to;
        dsu.queries[from].push_back({from, to, i});
        dsu.queries[to].push_back({to, from, i});
    }

    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return dist[x] > dist[y];
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        for (const auto &[u, d] : g[perm[i]])
        {
            if (dist[perm[i]] <= dist[u])
            {
                dsu.connect(perm[i], u, dist[perm[i]]);
            }
        }
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= m ; ++i)
    {
        int u, v, d;
        std::cin >> u >> v >> d;
        g[u].push_back({v, d});
        g[v].push_back({u, d});
    }

    std::cin >> k;
    npp.resize(k);

    for (int i = 0 ; i < k ; ++i)
    {
        std::cin >> npp[i];
        // std::cout << "here: " << npp[i] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

/*  
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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