제출 #1131805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131805		_DaNeK_	Evacuation plan (IZhO18_plan)	C++20	31 / 100	574 ms	499376 KiB

plan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define bust ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
const int INF = (ll) 1e9 + 10;
const int N = 1e5 + 44;
const int LOG = 20;
const int SZ = 835;
const int mod = 1e9 + 7;
const ld eps = 1e-12;

vector<pair<int,int>> g[N], v;
vector<int> nwg[N];
vector<int> npp;
map<int,pair<int,int>> changed;
int dist[N], p[N], sz[N], bp[604][N], bsz[604][N], aa[N], ap[N], asz[N], kk;

int fndp(int x) {
    if (p[x] == x) return x;
    return p[x] = fndp(p[x]);
}

void unite(int a, int b) {
    a = fndp(a);
    b = fndp(b);
    if (a == b) return ;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[b] = a;
    return ;
}

int fndp(int lvl, int a) {
    if (bp[lvl][a] == a) return a;
    return fndp(lvl, bp[lvl][a]);
}

void unite (int lvl, int a, int b) {
    a = fndp(lvl, a);
    b = fndp(lvl, b);
    if (a == b) return ;
    if (bsz[lvl][a] < bsz[lvl][b]) swap(a, b);
    int oldp = bp[lvl][b], oldsz = bsz[lvl][a];
    bsz[lvl][a] += bsz[lvl][b];
    bp[lvl][b] = a;
    aa[kk] = a;
    ap[kk] = bp[lvl][a];
    asz[kk] = oldsz;
    ++kk;
    aa[kk] = b;
    ap[kk] = oldp;
    asz[kk] = bsz[lvl][b];
    ++kk;
    if (!changed.count(a)) changed[a] = {bp[lvl][a], oldsz};
    if (!changed.count(b)) changed[b] = {oldp, bsz[lvl][b]};
    return ;
}

void dijkstra(int n) {
    fill(dist, dist + n, INF);
    priority_queue<pair<int,int>> q;
    for (int i : npp) {
        dist[i] = 0;
        q.push({0, i});
    }
    pair<int,int> p;
    while(!q.empty()) {
        p = q.top();
        int d = -p.fi, v = p.se;
        q.pop();
        if (dist[v] != d) continue ;
        for (auto &[to, w] : g[v]) {
            if (dist[to] > dist[v] + w) {
                dist[to] = dist[v] + w;
                q.push({-dist[to], to});
            }
        }
    }
    return ;
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        g[i].clear();
        nwg[i].clear();
        p[i] = i;
        sz[i] = 1;
    }
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[v].pb({u, w});
        g[u].pb({v, w});
    }
    int k;
    cin >> k;
    npp.resize(k);
    for (int & i : npp) {
        cin >> i;
        --i;
    }
    dijkstra(n);
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        v[i] = {dist[i], i};
    }
    for (int i = 0; i < n; ++i) {
        for (auto &[to, d] : g[i]) {
            if (dist[to] >= dist[i])
                nwg[i].pb(to);
        }
    }
    sort(all(v));
    reverse(all(v));
    int cur = 0, cnt = 0;
    vector<pair<int,int>> ord;
    for (int i = 0; i < n; ++i) {
        for (int to : nwg[v[i].se]) {
            if (dist[to] > dist[v[i].se] || (dist[to] == dist[v[i].se] && to > v[i].se)) {
                if (cnt % SZ == 0) {
                    for (int j = 0; j < n; ++j) {
                        bp[cur][j] = fndp(j);
                        bsz[cur][j] = sz[j];
                    }
                    ++cur;
                }
                ++cnt;
                //cout << v[i].se << " " << to << "\n";
                ord.pb({v[i].se, to});
                unite(to, v[i].se);
            }
        }
    }
    for (int j = 0; j < n; ++j) {
        bp[cur][j] = 0;
        bsz[cur][j] = n;
    }
    int q;
    cin >> q;
    while(q--) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        int lvl = -1;
        for (int i = 0; i < cur; ++i) {
            if (bp[i][a] != bp[i][b] && bp[i + 1][a] == bp[i + 1][b]) {
                lvl = i;
                break;
            }
        }
        if (lvl == -1) {
            cout << "-1\n";
            continue ;
        }
        //cout << lvl << " ";
        int ans = INF;
        kk = 0;
        for (int i = lvl * SZ; ; ++i) {
            if (i == ord.size()) {
                cout << "-1\n";
                break ;
            }
            ans = dist[ord[i].fi];
            unite(lvl, ord[i].fi, ord[i].se);
            if (fndp(lvl, bp[lvl][a]) == fndp(lvl, bp[lvl][b])) {
                cout << ans << "\n";
                break ;
            }
        }
        for (int i = kk; i >= 0; --i) {
            bp[lvl][aa[i]] = ap[i];
            bsz[lvl][aa[i]] = asz[i];
        }
    }

    return ;
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
1
5 3
*/

int main()
{
    //freopen ("input-slotmachine-c952.txt", "r", stdin);
    //freopen ("output.txt", "w", stdout);
    bust
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
        //cout << "Case #" << i << ": ";
        solve ();
    }
    return 0;
}

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