Submission #890664

#	Time	Username	Problem	Language	Result	Execution time	Memory
890664		aykhn	Evacuation plan (IZhO18_plan)	C++17	100 / 100	692 ms	80180 KiB

plan

#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcountll
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

struct DSU
{
    vector<int> e;
    void init(int n)
    {
        e.assign(n + 1, -1);
    }
    int get(int x)
    {
        if (e[x] < 0) return x;
        return e[x] = get(e[x]);
    }
    int tog(int x, int y)
    {
        return get(x) == get(y);
    }
    int unite(int x, int y)
    {
        x = get(x);
        y = get(y);
        if (x == y) return 0;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return 1;
    }
};

const int MXN = 5e5 + 5;

int n, m;
vector<array<int, 2>> adj[MXN];
int dist[MXN];
int l[MXN], r[MXN];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) dist[i] = inf;
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i][1] >> e[i][2] >> e[i][0];
        adj[e[i][1]].pb({e[i][2], e[i][0]});
        adj[e[i][2]].pb({e[i][1], e[i][0]});
    }
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    int k;
    cin >> k;
    while (k--)
    {
        int x;
        cin >> x;
        dist[x] = 0;
        pq.push({0, x});
    }
    while (!pq.empty())
    {
        array<int, 2> from = pq.top();
        pq.pop();
        if (from[0] > dist[from[1]]) continue;
        for (array<int, 2> v : adj[from[1]])
        {
            if (dist[v[0]] > from[0] + v[1])
            {
                dist[v[0]] = from[0] + v[1];
                pq.push({dist[v[0]], v[0]});
            }
        }
    }
    for (int i = 0; i < m; i++) e[i][0] = min(dist[e[i][1]], dist[e[i][2]]);
    sort(e.rbegin(), e.rend());
    int Q;
    cin >> Q;
    vector<array<int, 2>> q(Q);
    for (int i = 0; i < q.size(); i++) cin >> q[i][0] >> q[i][1], l[i] = 0, r[i] = 1e9;
    for (int lg = 0; lg < 31; lg++)
    {
        DSU dsu;
        dsu.init(n);
        vector<array<int, 2>> b;
        for (int i = 0; i < q.size(); i++) b.pb({(l[i] + r[i]) >> 1, i});
        sort(b.rbegin(), b.rend());
        int j = 0;
        for (int i = 0; i < b.size(); i++)
        {
            int id = b[i][1];
            while (j < e.size() && e[j][0] >= b[i][0]) dsu.unite(e[j][1], e[j][2]), j++;
            if (dsu.tog(q[id][0], q[id][1])) l[id] = b[i][0];
            else r[id] = b[i][0];
        }
    }
    for (int i = 0; i < q.size(); i++) cout << l[i] << '\n';
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:98:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0; i < q.size(); i++) cin >> q[i][0] >> q[i][1], l[i] = 0, r[i] = 1e9;
      |                     ~~^~~~~~~~~~
plan.cpp:104:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int i = 0; i < q.size(); i++) b.pb({(l[i] + r[i]) >> 1, i});
      |                         ~~^~~~~~~~~~
plan.cpp:107:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int i = 0; i < b.size(); i++)
      |                         ~~^~~~~~~~~~
plan.cpp:110:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             while (j < e.size() && e[j][0] >= b[i][0]) dsu.unite(e[j][1], e[j][2]), j++;
      |                    ~~^~~~~~~~~~
plan.cpp:115:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < q.size(); i++) cout << l[i] << '\n';
      |                     ~~^~~~~~~~~~

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