Submission #1370775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370775		vuviet	Evacuation plan (IZhO18_plan)	C++20	Compilation error	0 ms	0 KiB

plan

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 1e6 + 5;
int n, m, k, q, x[maxn], lo[maxn], hi[maxn];
long long res[maxn], d[maxn];
vector<pair<int, int>> graph[maxn];

struct DisjointSets
{
    int sz;
    vector<int> lab;

    DisjointSets(int sz)
    {
        this->sz = sz;
        lab.resize(sz + 5, -1);
    }

    int findset(int u)
    {
        return lab[u] < 0 ? u : lab[u] = findset(lab[u]);
    }

    void unite(int r, int s)
    {
        r = findset(r), s = findset(s);
        if (r == s) return;
        if (lab[r] > lab[s]) swap(r, s);
        lab[r] += lab[s], lab[s] = r;
    }
};

struct Edge
{
    int u, v, w;
    bool operator < (Edge o) const {
        return w > o.w;
    }
} e[maxn], qr[maxn];

void ReadData()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    cin >> k;
    for (int i = 1; i <= k; ++i)
        cin >> x[i];
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        cin >> qr[i].u >> qr[i].v;
        lo[i] = 1, hi[i] = m;
    }
}

void Dijkstra()
{
    priority_queue<pair<long long, int>> pq;
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= k; ++i)
        pq.push({0, x[i]}), d[x[i]] = 0;
    while (!pq.empty())
    {
        long long cur = -pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (cur != d[u]) continue;
        for (auto child : graph[u])
        {
            int v = child.first, w = child.second;
            if (d[v] > d[u] + w)
                d[v] = d[u] + w, pq.push({-d[v], v});
        }
    }
}

void Solve()
{
    Dijkstra();
    for (int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        e[i] = {u, v, min(d[u], d[v])};
    }
    sort(e + 1, e + 1 + m);
    int o = 1;
    while (o-- > 0)
    {
        vector<vector<int>> queries(m + 5);
        for (int i = 1; i <= q; ++i)
            if (lo[i] <= hi[i])
                queries[(lo[i] + hi[i]) / 2].push_back(i), t = o;

        DisjointSets dsu(n);
        for (int i = 1; i <= m; ++i)
        {
            dsu.unite(e[i].u, e[i].v);
            for (int id : queries[i])
                if (dsu.findset(qr[id].u) == dsu.findset(qr[id].v)) {
                    res[id] = e[i].w, hi[id] = i - 1;
                } else {
                    lo[id] = i + 1;
                }
        }
    }
    for (int i = 1; i <= q; ++i)
        cout << min({d[qr[i].u], d[qr[i].v], res[i]}) << "\n";
}

int main()
{
    ReadData();
    Solve();
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void Solve()':
plan.cpp:93:26: warning: narrowing conversion of '(long long int)std::min<long long int>(d[u], d[v])' from 'long long int' to 'int' [-Wnarrowing]
   93 |         e[i] = {u, v, min(d[u], d[v])};
      |                       ~~~^~~~~~~~~~~~
plan.cpp:102:60: error: 't' was not declared in this scope
  102 |                 queries[(lo[i] + hi[i]) / 2].push_back(i), t = o;
      |                                                            ^