제출 #1154366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154366		arkanefury	Evacuation plan (IZhO18_plan)	C++20	100 / 100	2196 ms	80180 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define lb lower_bound
#define F first
#define S second
#define sz size()
#define int long long
#define all(v) v.begin(),v.end()
#define FOR1(x, n) for(int j = x; j <= n; j ++)
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N =  1e6+5;
int b[N], a[N], c[N];
int n,m,k,sum=0,x,y, ans[N], r,pref[N], cnt, l, mod = 1e9+7, cal,L[N], R[N], p[N], d[N];
bool used[N];
vector<pair<int, int>>vec, check, g[N], query;
int par(int x){
    while(x!=p[x])x=p[x];
    return x;
}
int unite(int x, int y){
    x = par(x), y = par(y);
    if(x==y)return 0;
    if(y > x)swap(x, y);
    p[y] = x;
    return 1;
}
void solve(){
    cin >> n >> m;
    FOR(i, 1, m, 1){
        cin >> a[i] >> b[i] >> c[i];
        g[a[i]].pb({b[i], c[i]}), g[b[i]].pb({a[i], c[i]});
    }
    FOR(i, 1, n, 1)d[i] = 1e9;
    cin >> k;
    set<pair<int, int>>st;
    FOR(i, 1, k, 1){
        cin >> x;
        d[x] = 0;
        st.in({x, 0});
    }
    while(st.sz){
        pair<int, int> ko = *st.begin();
        st.erase(ko);
        for(auto i : g[ko.F]){
            if( ko.S + i.S < d[i.F] ){
                st.erase({i.F, d[i.F]});
                d[i.F] = ko.S + i.S;
                st.in({i.F, d[i.F]});
            }
        }
    }
    int q;
    cin >> q;
    FOR(i, 1, q, 1){
        cin >> x >> y;
        query.pb({x, y});
        L[i] = 1, R[i] = 1e9;
    }
    FOR(i, 1, m, 1){
        vec.pb( { min(d[a[i]], d[b[i]]), i } );
    }
    vec.pb({-1, -1});
    sort(all(vec));
    cnt = 0;
    while(1){
        cnt++;
        bool f = 0;
        FOR(i, 1, n, 1)p[i] = i;
        FOR(i, 1, q, 1){
            if(L[i] <= R[i])check.pb({ (L[i] + R[i]) >> 1, i }), f = 1;
        }
        if(!f)break;
        sort(all(check));
        reverse(all(check));
        int left = vec.sz-1;
        for(auto i : check){
            while(vec[left].F >= i.F){
                unite(a[vec[left].S], b[vec[left].S]), left --;
            }
            if( par( query[i.S-1].F ) == par( query[i.S-1].S ) ) L[i.S] = i.F + 1, ans[i.S] = i.F;
            else R[i.S] =  i.F - 1;
        }
        check.clear();
    }
    FOR(i, 1, q, 1)cout << ans[i] << '\n';
}
signed main(){
    nikita
    int tt = 1;
    if(!tt)cin >> tt;
    FOR(i, 1, tt, 1)solve();
}

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