Submission #514531

#	Time	Username	Problem	Language	Result	Execution time	Memory
514531		uHyHn	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4016 ms	42780 KiB

plan

#include<bits/stdc++.h>

//IBOW
#define Task "IZhO18_plan"
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define eb emplace_back
#define ll long long

using namespace std;

const int N = 2e5 + 10;
const int inf = 2e9 + 10;
const ll INF = 2e18 + 10;
const int MOD = 1e9 + 7;

/*

*/

int n, m, f[N], k, dist[N], q;
vector<pair<int, int>> g[N];
vector<int> edges[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void Deogiaibalamcho()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
        edges[u].pb(v);
        edges[v].pb(u);
    }
    for (int i = 1; i <= n; ++i) sort(all(edges[i]));
    fill(&dist[0], &dist[0] + N, inf);
    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        cin >> f[i];
        pq.push({0, f[i]});
        dist[f[i]] = 0;
    }
    while (!pq.empty())
    {
        pair<int, int> u = pq.top();
        pq.pop();
        if (u.F != dist[u.S]) continue;
        for (pair<int, int> e : g[u.S])
        {
            if (dist[e.F] > u.F + e.S)
            {
                dist[e.F] = u.F + e.S;
                pq.push({dist[e.F], e.F});
            }
        }
    }
//    for (int i = 1; i <= n; ++i) cout << dist[i] << ' ';
//    cout << '\n';
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (*lower_bound(all(edges[u]), v) == v)
            cout << min(dist[u], dist[v]) << '\n';
        else
        {
            int L = 1, R = 1e9, ans = 0;
            while (L <= R)
            {
                int mid = (L + R) / 2;
                queue<int> q;
                vector<int> d(n + 1, -1);
                if (dist[u] >= mid)
                {
                    q.push(u);
                    d[u] = 0;
                }
                while (!q.empty())
                {
                    int u = q.front();
                    q.pop();
                    for (pair<int, int> e : g[u])
                    {
                        if (d[e.F] == -1 && dist[e.F] >= mid)
                        {
                            d[e.F] = d[u] + 1;
                            q.push(e.F);
                        }
                    }
                }
//                cout << mid << ' ' << d[u] << '\n';
                if (d[v] != -1) ans = mid, L = mid + 1;
                else R = mid - 1;
            }
            cout << ans << '\n';
        }
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen(Task".inp", "r"))
    {
        freopen(Task".inp", "r", stdin);
//        freopen(Task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t--) Deogiaibalamcho();
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int32_t main()':
plan.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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