Submission #651946

#	Time	Username	Problem	Language	Result	Execution time	Memory
651946		vovik	Evacuation plan (IZhO18_plan)	C++17	100 / 100	640 ms	55924 KiB

plan

//I wrote this code 4 u today
#include <bits/stdc++.h>
 
#define vc vector
 
#define nd node*
#define pnd pair<nd, nd>
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;
 
template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};
 
 
template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}
 
template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}
 
template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}
 
const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;
 
const int N = 1e5 + 1, Q = 1e5 + 1;
vc<pair<int, int>> g[N];
 
vc<pair<int, int>> paths[N];
set<int> who[N];
int sz[N], p[N];
 
int get(int v) { return v == p[v] ? v : p[v] = get(p[v]); }
 
int ans[Q];
 
void merge(int v, int u, int c) {
    v = get(v), u = get(u);
    if (v == u) return;
    if (sz[v] < sz[u]) swap(v, u);
    for (auto [x, i]: paths[u]) if (who[v].count(x)) ans[i] = max(ans[i], c);
    p[u] = v;
    sz[v] = max(sz[v], sz[u] + 1);
    for (auto x : paths[u]) paths[v].push_back(x);
    for (auto &x: who[u]) who[v].insert(x);
}
 
int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    iota(p, end(p), 0);
    int n, m;
    cin >> n >> m;
    for (int v = 1; v <= n; ++v) who[v].insert(v);
    for (int a, b, w; m-- && (cin >> a >> b >> w);) g[a].emplace_back(b, w), g[b].emplace_back(a, w);
    vc<int> d(n + 1, INF);
    {
        int k;
        cin >> k;
        priority_queue<pair<int, int>, vc<pair<int, int>>, greater<>> q;
        for (int v; k--;) cin >> v, d[v] = 0, q.emplace(0, v);
        while (!q.empty()) {
            auto [c, v] = q.top();
            q.pop();
            if (d[v] != c) continue;
            for (auto [to, x]: g[v]) if (d[to] > c + x) d[to] = c + x, q.emplace(c + x, to);
        }
    }
    int q;
    cin >> q;
    for (int a, b, i = 0; i < q; ++i) cin >> a >> b, paths[a].emplace_back(b, i), paths[b].emplace_back(a, i);
    vc<int> vertices(n);
    iota(vertices.begin(), vertices.end(), 1);
    sort(vertices.begin(), vertices.end(), [&](const auto &v, const auto &u) { return d[v] > d[u]; });
    for (auto v: vertices) for (auto [to, w]: g[v]) if (d[v] <= d[to]) merge(v, to, d[v]);
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:72:22: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '9023372036854775808' to '1156317184' [-Woverflow]
   72 |     vc<int> d(n + 1, INF);
      |                      ^~~

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