Submission #1288423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288423		quangminh412	Evacuation plan (IZhO18_plan)	C++17	100 / 100	797 ms	29332 KiB

plan

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

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }

    solve();

    return 0;
}

// main program
const int oo = 0x3f3f3f3f;
const int maxn = 1e5 + 1;

struct DSU
{
    vector<int> par, sz;
    int n;

    DSU(int n) : n(n)
    {
        par.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++)
            par[i] = i;
    }

    void reset()
    {
        for (int i = 1; i <= n; i++)
        {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find(int u) { return (u == par[u] ? u : par[u] = find(par[u])); }
    bool same(int u, int v) { return find(u) == find(v); }

    void merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        if (sz[u] > sz[v])
            swap(u, v);
        par[u] = v;
        sz[v] += sz[u];
    }
};

vector<pair<int, int>> adj[maxn];
int g[maxn], dist[maxn];
int n, m, k, q;

void multisource_dijkstra()
{
    for (int i = 1; i <= n; i++)
        dist[i] = oo;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 1; i <= k; i++)
    {
        int u = g[i];
        dist[u] = 0;
        pq.push({dist[u], u});
    }

    while (!pq.empty())
    {
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();

        if (dist[u] != w)
            continue;

        for (pair<int, int> nxt : adj[u])
        {
            int v = nxt.first;
            if (dist[v] > w + nxt.second)
                pq.push({dist[v] = w + nxt.second, v});
        }
    }
}

vector<int> values, queries[maxn];
vector<pair<int, int>> save;
int ans[maxn], L[maxn], R[maxn], S[maxn], T[maxn];
int N;

void parallel_binarysearch()
{
    DSU dsu(n);
    while (1)
    {
        bool parallel = false;
        for (int i = 1; i <= q; i++)
            if (L[i] <= R[i])
            {
                queries[L[i] + R[i] >> 1].push_back(i);
                parallel = true;
            }
        if (!parallel)
            break;
        dsu.reset();
        int cursor = 0;
        for (int i = N - 1; i >= 0; i--)
        {
            int lim = values[i];
            while (cursor < n && save[cursor].first >= lim)
            {
                int u = save[cursor].second;
                for (pair<int, int> nxt : adj[u])
                {
                    int v = nxt.first;
                    if (dist[v] >= lim)
                        dsu.merge(u, v);
                }
                cursor++;
            }
            for (int idx : queries[i])
            {
                if (dsu.same(S[idx], T[idx]))
                {
                    ans[idx] = values[i];
                    L[idx] = i + 1;
                } else
                    R[idx] = i - 1;
            }
            queries[i].clear();
        }
    }
}

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

    multisource_dijkstra();

    for (int i = 1; i <= n; i++)
    {
        values.push_back(dist[i]);
        save.push_back({dist[i], i});
    }
    sort(values.begin(), values.end());
    sort(save.begin(), save.end(), greater<pair<int, int>>());
    values.erase(unique(values.begin(), values.end()), values.end());
    N = (int)values.size();

    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> S[i] >> T[i];
        L[i] = 0;
        R[i] = N - 1;
    }

    parallel_binarysearch();

    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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