Submission #162896

#	Time	Username	Problem	Language	Result	Execution time	Memory
162896		mrboorger	Evacuation plan (IZhO18_plan)	C++14	100 / 100	688 ms	30384 KiB

plan

//#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define sqr(x) (x) * (x)

using namespace std;
using namespace __gnu_pbds;

const int maxn = 1e5 + 2;
const int inf = 1e9 + 33333;
const int rt = 1e9;

struct DSU
{
    int boss[maxn];
    int rnk[maxn];
    DSU()
    {
        for(int i = 0; i < maxn; ++i)
        {
            boss[i] = i;
            rnk[i] = 1;
        }
    }
    void clear()
    {
        for(int i = 0; i < maxn; ++i)
        {
            boss[i] = i;
            rnk[i] = 1;
        }
        return;
    }
    int get(int x)
    {
        if (boss[x] == x) return x;
        return boss[x] = get(boss[x]);
    }
    void unite(int x, int y)
    {
        x = get(x);
        y = get(y);
        if (x == y) return;
        if (boss[y] > boss[x]) swap(x, y);
        rnk[x] += rnk[y];
        boss[y] = boss[x];
        return;
    }
};

struct zapros
{
    int num, x, y;
    zapros(int a, int b, int c)
    {
        num = a;
        x = b;
        y = c;
    }
};

vector <pair <int, int>> g[maxn];
vector <pair <int, pair <int, int>>> e;
int d[maxn];
int mid;
DSU snm;
int otv[maxn * 5];

int main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        --x;
        --y;
        e.pb({z, {x, y}});
        g[x].pb({y, z});
        g[y].pb({x, z});
    }
    fill(d, d + n, inf);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair <int, int>>> q;
    int k;
    cin >> k;
    for(int i = 0; i < k; ++i)
    {
        int x;
        cin >> x;
        --x;
        d[x] = 0;
        q.push({0, x});
    }
    while(!q.empty())
    {
        int val = q.top().F;
        int v = q.top().S;
        q.pop();
        if (val > d[v]) continue;
        for(pair <int, int> to : g[v])
        {
            if (d[to.F] > val + to.S)
            {
                d[to.F] = val + to.S;
                q.push({val + to.S, to.F});
            }
        }
    }

    for(int i = 0; i < m; ++i)
        e[i].F = min(d[e[i].S.F], d[e[i].S.S]);
    sort(e.rbegin(), e.rend());

    int Q;
    cin >> Q;
    queue <pair <int, int>> ql;
    queue <vector <zapros>> qv;
    vector <zapros> cl;
    ql.push({0, rt});
    qv.push(cl);
    for(int ii = 0; ii < Q; ++ii)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        qv.front().pb(zapros(ii, x, y));
    }


    int R = rt;
    int uk = 0;
    while(!ql.empty())
    {
        if (qv.front().size() == 0)
        {
            ql.pop();
            qv.pop();
            continue;
        }
        int l = ql.front().F, r = ql.front().S;
        mid = (l + r) / 2;
        if (mid > R)
        {
            uk = 0;
            snm.clear();
        }

        while(uk < m && e[uk].F >= mid)
        {
            snm.unite(e[uk].S.F, e[uk].S.S);
            ++uk;
        }
        vector <zapros> lft;
        vector <zapros> rht;

        for(int i = 0; i < int(qv.front().size()); ++i)
        {
            int x = qv.front()[i].x;
            int y = qv.front()[i].y;
            int num = qv.front()[i].num;
            if (snm.get(x) == snm.get(y))
            {
                otv[num] = max(otv[num], mid);
                rht.pb(qv.front()[i]);
            }
            else
            {
                lft.pb(qv.front()[i]);
            }
        }

        ql.pop();
        qv.pop();
        R = mid;
        if (l < r)
        {
            ql.push({mid + 1, r});
            qv.push(rht);
            ql.push({l, mid - 1});
            qv.push(lft);
        }
    }


    for(int i = 0; i < Q; ++i)
        cout << otv[i] << '\n';
    return 0;
}

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