Submission #91716

#	Time	Username	Problem	Language	Result	Execution time	Memory
91716		popovicirobert	Evacuation plan (IZhO18_plan)	C++14	100 / 100	959 ms	26068 KiB

plan

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int INF = 1e9;
const int MAXN = (int) 1e5;

vector < pair <int, int> > g[MAXN + 1];
int bad[MAXN + 1];
int n, m, q;

bool inq[MAXN + 1];
int dist[MAXN + 1];

inline void BF(int k) {
    queue <int> Q;
    for(int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    for(int i = 1; i <= k; i++) {
        Q.push(bad[i]);
        dist[bad[i]] = 0;
        inq[bad[i]] = 1;
    }
    while(Q.size()) {
        int nod = Q.front();
        inq[nod] = 0;
        Q.pop();
        for(auto it : g[nod]) {
            if(dist[it.first] > dist[nod] + it.second) {
                dist[it.first] = dist[nod] + it.second;
                if(!inq[it.first]) {
                    inq[it.first] = 1;
                    Q.push(it.first);
                }
            }
        }
    }
}

struct DSU {
    vector <int> par;
    inline void init(int n) {
        par.resize(n + 1);
    }
    inline int myfind(int x) {
        if(par[x] == 0)
            return x;
        return par[x] = myfind(par[x]);
    }
    inline void myunion(int x, int y) {
        x = myfind(x), y = myfind(y);
        if(x != y) {
            par[x] = y;
        }
    }
};

struct Edge {
    int x, y;
    int cst;
    bool operator <(const Edge &other) const {
        return cst > other.cst;
    }
};

vector <Edge> edges;

pair <int, int> res[MAXN + 1], qry[MAXN + 1];
int sol[MAXN + 1];

inline void solve(int step)  {
    DSU dsu;
    dsu.init(n);
    sort(res + 1, res + q + 1);
    int pos = 0;
    for(int i = q; i >= 1; i--) {
        while(pos < m && edges[pos].cst >= res[i].first + step) {
            dsu.myunion(edges[pos].x, edges[pos].y);
            pos++;
        }
        if(dsu.myfind(qry[res[i].second].first) == dsu.myfind(qry[res[i].second].second)) {
            res[i].first += step;
        }
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
        edges.push_back({a, b, 0});
    }
    cin >> k;
    for(i = 1; i <= k; i++) {
        cin >> bad[i];
    }
    BF(k);
    for(i = 0; i < m; i++) {
        edges[i].cst = min(dist[edges[i].x], dist[edges[i].y]);
    }
    sort(edges.begin(), edges.end());
    cin >> q;
    for(i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        qry[i] = {a, b};
        res[i] = {0, i};
    }
    for(int step = 1 << 30; step; step >>= 1) {
        solve(step);
    }
    for(i = 1; i <= q; i++) {
        sol[res[i].second] = res[i].first;
    }
    for(i = 1; i <= q; i++) {
        cout << sol[i] << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

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