Submission #492352

#	Time	Username	Problem	Language	Result	Execution time	Memory
492352		Rainbowbunny	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1075 ms	32388 KiB

plan

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

const int MAXN = 1e5 + 5;
const int INF = 1e9;

int n, m, k, q;
int d[MAXN];
int l[MAXN], r[MAXN];
int uu[MAXN], vv[MAXN], dsu[MAXN];
vector <pair <int, int> > Adj[MAXN];

int Root(int node)
{
    return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        Adj[u].emplace_back(v, c);
        Adj[v].emplace_back(u, c);
    }
    for(int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }
    priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int a;
        cin >> a;
        d[a] = 0;
        pq.emplace(0, a);
    }
    while(pq.empty() == false)
    {
        int dd = pq.top().first, node = pq.top().second;
        pq.pop();
        if(dd == d[node])
        {
            for(auto x : Adj[node])
            {
                if(d[x.first] > d[node] + x.second)
                {
                    d[x.first] = d[node] + x.second;
                    pq.emplace(d[x.first], x.first);
                }
            }
        }
    }
    vector <pair <int, int> > V;
    for(int i = 1; i <= n; i++)
    {
        V.emplace_back(d[i], i);
    }
    sort(V.rbegin(), V.rend());
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> uu[i] >> vv[i];
        l[i] = 0, r[i] = 1e9;
    }
    for(int times = 1; times <= 30; times++)
    {
        vector <pair <int, int> > Queries;
        for(int i = 1; i <= n; i++)
        {
            dsu[i] = i;
        }
        for(int i = 1; i <= q; i++)
        {
            int mid = (l[i] + r[i] + 1) >> 1;
            Queries.emplace_back(mid, i);
        }
        sort(Queries.rbegin(), Queries.rend());
        int pt = 0;
        for(auto x : Queries)
        {
            while(pt < n and V[pt].first >= x.first)
            {
                for(auto x : Adj[V[pt].second])
                {
                    int u = x.first, v = V[pt].second;
                    if(d[u] >= d[v])
                    {
                        u = Root(u), v = Root(v);
                        if(u != v)
                        {
                            dsu[u] = v;
                        }
                    }
                    
                }
                pt++;
            }
            if(Root(uu[x.second]) == Root(vv[x.second]))
            {
                l[x.second] = x.first;
            }
            else
            {
                r[x.second] = x.first - 1;
            }
        }
    }
    for(int i = 1; i <= q; i++)
    {
        cout << l[i] << '\n';
    }
}

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