Submission #958690

#	Time	Username	Problem	Language	Result	Execution time	Memory
958690		I_am_Polish_Girl	Evacuation plan (IZhO18_plan)	C++14	100 / 100	909 ms	82216 KiB

plan

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>

using namespace std;

#define int long long

int log_ = 10;
int inf = 1000000000000000000;
int mod = 998244353;

vector < vector< pair <int , int > > > g;

vector <int> link;
vector <int> w;

int find(int u)
{
    if (link[u] == u)
        return u;

    link[u] = find(link[u]);
    return link[u];
}


void merge(int u, int v)
{
    u = find(u);
    v = find(v);

    if (u == v)
        return;

    if (w[u] < w[v])
        swap(u, v);

    link[v] = u;
    w[u] += w[v];
}

void init(int n)
{
    link.clear();
    w.clear();


    link.resize(n);
    w.resize(n , 1);

    for (int i = 0; i < n; i++)
        link[i] = i;
}






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

    int n , m;
    cin >> n >> m;

    g.resize(n);

    vector < pair <int , int> > edges(m);

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;


        edges[i] = { u , v };

        g[u].push_back({ v , w });
        g[v].push_back({ u , w });
    }


    priority_queue < pair <int, int> > pq;

    vector <int> deep(n , inf);

    int k;
    cin >> k;
    
    for (int i = 0; i < k; i++)
    {
        int u;
        cin >> u;
        u--;

        deep[u] = 0;
        pq.push({ 0 , u });
    }

    while (pq.size() > 0)
    {
        int ind = pq.top().second;
        int d = -pq.top().first;

        pq.pop();

        if (deep[ind] < d)
            continue;


        for (int i = 0; i < g[ind].size(); i++)
        {
            int ind_s = g[ind][i].first;
            int d_ = g[ind][i].second;

            if (deep[ind_s] > deep[ind] + d_)
            {
                deep[ind_s] = deep[ind] + d_;

                pq.push({ -deep[ind_s] , ind_s });
            }
        }
    }


    vector < pair <int , pair <int , int>> > ed;

    for (int i = 0; i < m; i++)
    {
        int u = edges[i].first;
        int v = edges[i].second;

        if (deep[u] < deep[v])
            swap(u, v);

        ed.push_back({deep[v] , {u , v}});
    }

    sort(ed.begin(), ed.end());

    int q_;
    cin >> q_;
    vector < pair <int, int> > q(q_);

    for (int i = 0; i < q_; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        q[i] = { u , v };
    }

    vector <int> l(q_ ,0);
    vector <int> r(q_ , m);

    vector <int> mid(q_);

    vector < vector <int> > m_(q_);


    for (int k = 0; k < 20; k++)
    {

        init(n);

        m_.clear();
        m_.resize(m);

        for (int i = 0; i < q_; i++)
        {
            if (r[i] - l[i] == 1)
            {
                continue;
            }

            mid[i] = (l[i] + r[i]) / 2;
            m_[mid[i]].push_back(i);
        }


        for (int i = m - 1; i >= 0; i--)
        {
            int u = ed[i].second.first;
            int v = ed[i].second.second;

            merge(u, v);

            for (int j = 0; j < m_[i].size(); j++)
            {
                int u_, v_;

                int ind = m_[i][j];

                u_ = q[ind].first;
                v_ = q[ind].second;

                if (find(u_) == find(v_))
                {
                    l[ind] = mid[ind];
                }
                else
                {
                    r[ind] = mid[ind];
                }
            }
        }
    }


    for (int i = 0; i < q_; i++)
    {
        int l_ = l[i];
        cout << ed[l_].first << "\n";
    }
}

/*
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
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:126:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for (int i = 0; i < g[ind].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
plan.cpp:205:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |             for (int j = 0; j < m_[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~

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