Submission #878358

#	Time	Username	Problem	Language	Result	Execution time	Memory
878358		heeheeheehaaw	Evacuation plan (IZhO18_plan)	C++17	100 / 100	325 ms	38396 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

int n, m, k, q;
const int INF = 1e9;
vector<pair<int, int>> adj[100005];
int dist[100005];
priority_queue<pair<int, int>> pq;
vector<int> qry[100005], parent;
vector<int> moment[100005], minm[100005];
int hei[100005], minn[100005], tin[100005];

void init()
{
    parent.resize(n + 1);
    for(int i = 1; i <= n; i++)
        parent[i] = i, hei[i] = 1, tin[i] = 0, minn[i] = dist[i];
}

int cauta(int u, int timer)
{
    if(parent[u] == u || tin[u] > timer)
        return u;
    return cauta(parent[u], timer);
}

bool cmp(int a, int b)
{
    return dist[a] > dist[b];
}

void unite(int u, int v, int t)
{
    u = cauta(u, t);
    v = cauta(v, t);
    if(u == v)
        return;
    if(hei[u] > hei[v])
        swap(u, v);
    moment[v].push_back(t);
    minn[v] = min(minn[v], minn[u]);
    minm[v].push_back(minn[v]);
    tin[u] = t;
    parent[u] = v;
    hei[v] = max(hei[v], hei[u] + 1);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    cin>>k;
    vector<int> aux;
    for(int i = 1; i <= n; i++)
        dist[i] = INF, aux.push_back(i);

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

    while(!pq.empty())
    {
        int nod = pq.top().second;
        int d = -pq.top().first;
        pq.pop();
        if(dist[nod] != d)
            continue;
        for(auto it : adj[nod])
            if(dist[nod] + it.second < dist[it.first])
                dist[it.first] = dist[nod] + it.second, pq.push({-dist[it.first], it.first});
    }

    init();
    sort(aux.begin(), aux.end(), cmp);
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        for(auto it : adj[aux[i]])
            if(dist[it.first] >= dist[aux[i]])
                unite(it.first, aux[i], ++cnt);
    }

    cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int a, b;
        cin>>a>>b;
        int st = 1, dr = cnt, rez, nod;
        while(st <= dr)
        {
            int mij = (st + dr) / 2;
            int u = cauta(a, mij), v = cauta(b, mij);
            if(u != v) st = mij + 1;
            else dr = mij - 1, rez = mij, nod = u;
        }

        int poz = upper_bound(moment[nod].begin(), moment[nod].end(), rez) - moment[nod].begin();
        cout<<min(min(dist[a], dist[b]), minm[nod][poz - 1])<<'\n';
    }


    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