Submission #894678

#	Time	Username	Problem	Language	Result	Execution time	Memory
894678		CyberCow	Evacuation plan (IZhO18_plan)	C++17	100 / 100	314 ms	34292 KiB

plan

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);

const int N = 100005;

vector<pair<int, int>> v[N];
int dist[N];

int p[N], sz[N];
int mecpapa;
int has[N];
int gggg[N];

void make_set(int i)
{
    p[i] = i;
    sz[i] = 1;
    gggg[i] = dist[i];
}

int get_papa(int i)
{
    if (p[i] == i)
        return i;
    return get_papa(p[i]);
}

vector<int> mde[N];


void union_set(int a, int b, int ggg)
{
    a = get_papa(a);
    b = get_papa(b);
    if (a == b) return;
    if (sz[a] < sz[b])
        swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
    mde[a].push_back(b);
    has[b] = a;
    gggg[b] = ggg;
    mecpapa = a;
}


int xorutyun[N];

void Dfs(int g, int xr)
{
    xorutyun[g] = xr;
    for (auto to : mde[g])
    {
        Dfs(to, xr + 1);
    }
}

void solve()
{
    int n, i, j, m, x, y, w;
    cin >> n >> m;
    for ( i = 0; i < m; i++)
    {
        cin >> x >> y >> w;
        v[x].push_back({ y, w });
        v[y].push_back({ x, w });
    }
    for ( i = 1; i <= n; i++)
    {
        dist[i] = 1e9;
    }
    int k;
    cin >> k;
    priority_queue<pair<int, int>> q;
    for ( i = 0; i < k; i++)
    {
        cin >> x;
        q.push({ 0, x });
        dist[x] = 0;
    }
    while (!q.empty())
    {
        pair<int, int> gag = q.top();
        q.pop();
        gag.first *= -1;
        if (gag.first > dist[gag.second])
            continue;
        for (auto to : v[gag.second])
        {
            if (gag.first + to.second < dist[to.first])
            {
                dist[to.first] = gag.first + to.second;
                q.push({-dist[to.first], to.first });
            }
        }
    }
    vector<pair<int, int>> hert;
    for ( i = 1; i <= n; i++)
    {
        hert.push_back({ dist[i], i });
        make_set(i);
    }
    sort(hert.begin(), hert.end());
    for ( i = hert.size() - 1; i >= 0; i--)
    {
        for (auto to : v[hert[i].second])
        {
            if (dist[to.first] >= hert[i].first)
            {
                union_set(to.first, hert[i].second, hert[i].first);
            }
        }
    }
    Dfs(mecpapa, 0);
    int qq;
    cin >> qq;
    for ( i = 0; i < qq; i++)
    {
        cin >> x >> y;
        int res = 1e9;
        while (x != y)
        {
            if (xorutyun[x] > xorutyun[y])
            {
                res = min(res, gggg[x]);
                x = has[x];
            }
            else
            {
                res = min(res, gggg[y]);
                y = has[y];
            }
        }
        cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:84:15: warning: unused variable 'j' [-Wunused-variable]
   84 |     int n, i, j, m, x, y, w;
      |               ^

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