Submission #1097697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097697		TrinhKhanhDung	Evacuation plan (IZhO18_plan)	C++14	100 / 100	299 ms	43592 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct DSU{
    vector<int> par, Sz;
    vector<vector<pair<int, int>>> ord;

    DSU(int n = 0){
        par.resize(n + 3, 0);
        ord.resize(n + 3);
        Sz.resize(n + 3, 1);
        for(int i = 1; i <= n; i++){
            par[i] = i;
        }
    }

    int root(int u){
        return u == par[u] ? u : par[u] = root(par[u]);
    }

    bool join(int a, int b){
        a = root(a);
        b = root(b);
        if(a == b) return false;
        if(Sz[a] < Sz[b]) swap(a, b);
        par[b] = a;
        Sz[a] += Sz[b];
        if(sz(ord[a]) < sz(ord[b])) ord[a].swap(ord[b]);
        for(auto x: ord[b]){
            ord[a].push_back(x);
        }
        return true;
    }
};

const int MAX_N = 1e5 + 10, MAX_M = 5e5 + 10;

int N, M, K, Q;
vector<pair<int, int>> adj[MAX_N];
int dist[MAX_N], ans[MAX_N];
bool mark[MAX_N];
vector<int> nyc;
vector<pair<int, int>> queries[MAX_N];

void solve(){
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    cin >> K;
    for(int i = 1; i <= K; i++){
        int x; cin >> x;
        nyc.push_back(x);
    }
    cps(nyc);
    cin >> Q;
    for(int i = 1; i <= Q; i++){
        int u, v;
        cin >> u >> v;
        queries[u].push_back({v, i});
        queries[v].push_back({u, i});
    }

    clock_t start = clock();

    //Dijkstra
    memset(dist, 0x3f, sizeof dist);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for(int x: nyc){
        dist[x] = 0;
        pq.push({0, x});
    }

    while(!pq.empty()){
        int u = pq.top().se;
        int kc = pq.top().fi;
        pq.pop();

        if(kc > dist[u]) continue;

        for(auto o: adj[u]){
            int v = o.fi;
            int newkc = kc + o.se;
            if(minimize(dist[v], newkc)){
                pq.push({dist[v], v});
            }
        }
    }

    DSU dsu(N);

    vector<pair<int, int>> ord;
    for(int i = 1; i <= N; i++){
        ord.push_back({dist[i], i});
        dsu.ord[i] = queries[i];
    }

    sort(ALL(ord), greater<pair<int, int>>());

    memset(ans, -1, sizeof ans);
    for(auto o: ord){
        int u = o.se, kc = o.fi;
        mark[u] = true;
        for(auto e: adj[u]){
            int v = dsu.root(e.fi);
            if(!mark[v] || u == v) continue;

            if(sz(dsu.ord[u]) < sz(dsu.ord[v])){
                for(auto q: dsu.ord[u]){
                    if(ans[q.se] != -1) continue;
                    if(dsu.root(q.fi) == v){
                        ans[q.se] = kc;
                    }
                }
            }
            else{
                for(auto q: dsu.ord[v]){
                    if(ans[q.se] != -1) continue;
                    if(dsu.root(q.fi) == u){
                        ans[q.se] = kc;
                    }
                }
            }

            dsu.join(u, v);
            u = dsu.root(u);
        }
    }

    for(int i = 1; i <= Q; i++){
        cout << ans[i] << '\n';
    }

    cerr << "Time elapsed: " << clock() - start << " ms\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("walk.inp","r",stdin);
//    freopen("walk.out","w",stdout);

    int t = 1;
//    cin >> t;
    while(t--)
        solve();

    return 0;
}

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