Submission #90911

#	Time	Username	Problem	Language	Result	Execution time	Memory
90911		toloraia	Evacuation plan (IZhO18_plan)	C++17	100 / 100	3823 ms	45816 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 5e5 + 5, INF = 1e9 + 5;

int n, m;
vector < int > g[N], gg[N];
int mas[N];
priority_queue < pair < int, int > > Q;
int q;
int s[N], f[N], l[N], r[N],  mid[N];
pair < int, int > P[N], PP[N];
bool F[N];
int p[N];
int parent (int x){
    if (p[x] == x)
        return x;
    return p[x] = parent (p[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    while (m--){
        int u, v, x;
        cin>>u>>v>>x;
        g[u].pb (v);
        gg[u].pb (x);
        g[v].pb (u);
        gg[v].pb (x);
    }
    for (int i = 1; i <= n; i++)
        mas[i] = INF;
    cin>>m;
    while (m--){
        int x;
        cin>>x;
        mas[x] = 0;
        Q.push ({-mas[x], x});
    }
    cin>>q;
    for (int i = 1; i <= q; i++){
        cin>>s[i]>>f[i];
        l[i] = 1;
        r[i] = n;
    }
    while (Q.size() > 0){
        int k = Q.top().S;
        Q.pop();
        if (F[k])
            continue;
        F[k] = 1;
        for (int i = 0; i < g[k].size(); i++){
            int to = g[k][i];
            if (mas[to] > mas[k] + gg[k][i]){
                mas[to] = mas[k] + gg[k][i];
                Q.push ({-mas[to], to});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        P[i] = {-mas[i], i};
    sort (P + 1, P + n + 1);
    for (int mtvleli = 0; mtvleli < 30; mtvleli++){
        for (int i = 1; i <= q; i++){
            mid[i] = (l[i] + r[i]) / 2;
            PP[i] = {mid[i], i};
        }
        sort (PP + 1, PP + q + 1);
        int I = 1;
        for (int i = 1; i <= n; i++){
            F[i] = 0;
            p[i] = i;
        }
        for (int i = 1; i <= n; i++){
            int u = P[i].S;
            F[u] = 1;
            for (int j = 0; j < g[u].size(); j++)
                if (F[g[u][j]] == 1){
                    parent (g[u][j]);
                    p[p[g[u][j]]] = u;
                }
            for (; I <= q && PP[I].F == i; I++){
                int k = PP[I].S;
                int u = s[k], v = f[k];
                parent(u);
                parent(v);
                if (p[u] == p[v])
                    r[k] = mid[k];
                else
                    l[k] = mid[k] + 1;
            }
        }
    }
    for (int i = 1; i <= q; i++)
        cout<<-P[l[i]].F<<endl;
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[k].size(); i++){
                         ~~^~~~~~~~~~~~~
plan.cpp:84:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[u].size(); j++)
                             ~~^~~~~~~~~~~~~

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