Submission #1268556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268556		Bui_Quoc_Cuong	Evacuation plan (IZhO18_plan)	C++20	100 / 100	477 ms	48864 KiB

plan

/* 29 . 03 . 2008 */ 
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,ll>> vii ;
typedef pair<long long,int> ii ;
#define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define all(a) a.begin() , a.end()
#define pb push_back
#define fi first
#define se second
#define BIT(mask,i) ((mask>>i)&1)
#define builtin_popcount builtin_popcountll
#define MASK(a) (1ll << a) 

template<class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
template<class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}

const int N = 5e5 + 5 ; 
const ll inf = 1e18 ;

int n , m , k , q ; 
int x[N] ; 
vii g[N] ;
ll dist[N] ;
struct Edges {
    int u , v , w ; 
} e[N] ;

void init() {
    cin >> n >> m; /// >> k >> q ; 
    FOR(i,1,m) {
        int u , v , w ; cin >> u >> v >> w ; 
        g[u].pb({v,w}) ; g[v].pb({u,w}) ; 
        e[i] = {u , v , w} ; 
    }
    cin >> k;
    FOR(i,1,k) cin >> x[i] ; 
    cin >> q;
}

void dijkstra() {
    priority_queue<ii,vector<ii>,greater<ii>> pq ; 
    FOR(i,1,n) dist[i] = inf ; 
    FOR(i,1,k) {
        dist[x[i]] = 0 ; 
        pq.push({0 , x[i]}) ; 
    }
    while(!pq.empty()) {
        auto [cost , u] = pq.top() ; 
        pq.pop() ; 
        if(cost > dist[u]) continue ; 
        for(auto [v,w] : g[u]) {
            if(mini(dist[v],cost+w)) { 
                pq.push({cost+w,v}) ; 
            }
        }
    }
}

bool check(ll mid,int st,int ed) {
    if(dist[ed] < mid) return 0 ;

    queue<int> q ;
    vector<int> vis ; 
    vis.resize(n + 2,0) ;

    if(dist[st] >= mid) q.push(st) , vis[st] = 1 ; 

    while(!q.empty()) {
        int u = q.front() ; 
        q.pop() ; 
        if(u==ed) return 1 ; 
        for(auto [v,w] : g[u]) {
            if(!vis[v] && dist[v] >= mid) {
                vis[v] = 1 ; 
                q.push(v) ; 
            }
        }
    }
    return 0 ;
}

namespace subtask_1 {

    void solve() {
        dijkstra() ; 

        while(q--) {
            int a , b ; cin >> a >> b ; 
            ll l = 0 , r = inf , ans = -1 ; 
            while(l <= r) {
                ll mid = (l+r)>>1 ; 
                if(check(mid,a,b)) ans = mid , l = mid + 1 ; 
                else r = mid - 1 ; 
            }   
            cout << ans << endl ;
        }
    }
}

namespace subtask_2 {
    ll ans[N] ;
    ll L[N] , R[N] ;
    ii Q[N] ;   
    ll deCompress[N] ;
    vi Quer[N] , pos[N] ; 
    unordered_map<ll,ll> cur ;

    struct DSU {
        int par[N] ; 

        int acs(int u) {
            if(u==par[u]) return u ; 
            else return par[u] = acs(par[u]) ; 
        }

        bool join(int u,int v) {
            int x = acs(u) , y = acs(v) ; 
            if(x==y) return 0 ;
            par[x] = y ; 
            return 1 ; 
        }
    } dsu ; 

    void solve() {
        dijkstra() ; 

        vi V ; 
        FOR(i,1,n) V.pb(dist[i]) ; 
        sort(all(V)) ;
        V.resize(unique(all(V))-V.begin()) ;
        int VAL = V.size() ; 
        FOR(i,0,VAL-1) deCompress[i + 1] = V[i] ; 

        FOR(i,1,m) {
            int u = e[i].u , v = e[i].v ; 
            ll w = min(dist[u],dist[v]) ; 
            int p = lower_bound(all(V),w) - V.begin() + 1 ; 
            pos[p].pb(i) ; 
        }

        FOR(i,1,q) {
            int a , b ; cin >> a >> b ;
            Q[i] = {a , b} ; 
            L[i] = 1 , R[i] = VAL ; 
        }   

        while(1) {
            FOR(i,1,n) dsu.par[i] = i ; 
            FOR(i,1,VAL) Quer[i].clear() ; 

            bool ok = false ; 
            FOR(i,1,q) if(L[i] <= R[i]) {
                ok = true ; 
                Quer[(L[i]+R[i])/2].pb(i) ; 
            }
            if(!ok) break ; 

            FORD(val,VAL,1) {
                for(auto id_edges : pos[val]) {
                    int u = e[id_edges].u , v = e[id_edges].v ; 
                    dsu.join(u,v) ;
                }
                for(auto id : Quer[val]) {
                    int u = Q[id].fi , v = Q[id].se ; 
                    if(dsu.acs(u)==dsu.acs(v)) {
                        L[id] = val + 1 ; 
                        ans[id] = val ; 
                    } else R[id] = val - 1 ; 
                }
            }
        }

        FOR(i,1,q) {
            cout << deCompress[ans[i]] << '\n' ; 
        }
    }
}

signed main() {
    #define task "walk"
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 
    if(fopen(".inp","r")) {
        freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ; 
    }
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ; 
    }
    init() ;
    if(n <= 1e3 && q <= 1e3) subtask_1::solve() ;
    else subtask_2::solve() ;
    cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
    return 0 ; 
}
/* Watbor */

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:188:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:191:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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