Submission #118679

#	Time	Username	Problem	Language	Result	Execution time	Memory
118679		Alexa2001	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2556 ms	29492 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5, Mmax = 5e5 + 5;
typedef pair<int,int> Pair;

Pair edge[Mmax], query[Nmax];
vector<Pair> v[Nmax];
bitset<Nmax> bad;
int res[Nmax], dist[Nmax], cost[Mmax];
int n, q, m;


struct 
{
    int t[Nmax];

    int boss(int x)
    {
        if(x == t[x]) return x;
        return t[x] = boss(t[x]);
    }

    void init()
    {
        int i;
        for(i=1; i<=n; ++i) t[i] = i;
    }

    bool same(int x, int y)
    {
        return boss(x) == boss(y);
    }

    bool unite(int x, int y)
    {
        x = boss(x);
        y = boss(y);
        if(x == y) return 0;
        t[x] = y;
        return 1;
    }
} uf;

void dijkstra()
{
    priority_queue<Pair, vector<Pair>, greater<Pair>> heap;

    int i;
    for(i=1; i<=n; ++i)
        if(bad[i]) dist[i] = 0, heap.push({0, i});
            else dist[i] = 1e9;

    while(heap.size())
    {
        int node, act_dist;
        tie(act_dist, node) = heap.top();
        heap.pop();

        if(dist[node] != act_dist) continue;

        for(auto it : v[node])
            if(dist[it.first] > act_dist + it.second)
            {
                dist[it.first] = act_dist + it.second;
                heap.push({dist[it.first], it.first});
            }
     }
}

void solve()
{
    int step, i;
    for(i=1; i<=q; ++i) res[i] = 0;
    
    vector<int> ord, ord_edges;
    for(i=1; i<=q; ++i) ord.push_back(i);
    for(i=1; i<=m; ++i) ord_edges.push_back(i), cost[i] = min(dist[edge[i].first], dist[edge[i].second]);

    ord_edges.push_back(m+1);
    cost[m+1] = 0;
    edge[m+1] = {1, 1};

    auto qcmp = [] (int x, int y)
    {
        return res[x] < res[y];
    };

    auto edge_cmp = [] (int x, int y)
    {
        return cost[x] > cost[y];
    };

    sort(ord_edges.begin(), ord_edges.end(), edge_cmp);

    for(step = (1<<30); step; step >>= 1)
    {
        vector<int> old = ord;

        uf.init();
        sort(ord.begin(), ord.end(), qcmp);

        for(auto it : ord_edges)
        {
            while(ord.size() && cost[it] < res[ord.back()] + step)
            {
                int id = ord.back();
                if(uf.same(query[id].first, query[id].second))
                    res[id] += step;
                ord.pop_back();
            }
            
            int x, y;
            tie(x, y) = edge[it];
            uf.unite(x, y);
        }
        
        assert(ord.empty());
        ord = old;
    }
    
  //  cerr << "W"; cerr << q << '\n';
    for(i=1; i<=q; ++i) cout << res[i] << '\n';
}

int main()
{
  //  freopen("data.in", "r", stdin);
    cin.sync_with_stdio(false);
    cin.tie(0);

    int x, y, i, len;

    cin >> n >> m;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y >> len;
        v[x].push_back({y, len});
        v[y].push_back({x, len});
        edge[i] = {x, y};
    }
    
//    cerr << "#";

    int k;
    cin >> k;
    while(k--)
    {
        cin >> x;
        bad[x] = 1;
    }

    dijkstra();

    cin >> q;
    for(i=1; i<=q; ++i)
    {
        cin >> x >> y;
        query[i] = {x, y};
    }

    solve();

    return 0;
}

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