Submission #210221

#	Time	Username	Problem	Language	Result	Execution time	Memory
210221		mohamedsobhi777	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4003 ms	73328 KiB

plan

#include<bits/stdc++.h> 

using namespace std ; 

const int N = 5e5 + 7 ; 

int n , m , k , q ; 
bool bad[N] ;
int root ;
vector<pair<int , int > > adj[N] ; 
priority_queue<pair<int , int > > Q; 
int d[N] ; 
vector<int> v ; 

void dijkstra(){
    memset(d , -1 , sizeof d) ; 
    for(auto u : v){
        d[u] = 0 ; 
    }
    while(Q.size()){
        int dst = -Q.top().first ; 
        int node = Q.top().second ;
        Q.pop()  ;
        for(auto u : adj[node]){
            if(d[u.first]==-1 || dst + u.second < d[u.first]){

                d[u.first] = dst + u.second ; 
                Q.push({-d[u.first] , u.first}) ; 
            }
        }
    }
}

int B  , t , limit; 
int vis[N] ;

int dfs(int x){
    if(vis[x]==t)
     return 0 ;
    vis[x] = t ; 
    for(auto u : adj[x])
    {
        if(d[u.first] >=limit && vis[u.first] !=t)
        dfs(u.first);
    }
}
    
map<pair<int , int > , bool > mp ; 


int main(){
  //  freopen("in.in" , "r" , stdin) ; 
    cin>>n >>m; 
    for(int i = 0 ; i < m ; i++){
        int a , b, c; 
        cin>>a>>b>>c ; 
        adj[a].push_back({b , c}) ; 
        adj[b].push_back({a , c}) ; 
        mp[{min(a , b ) , max(a , b)}] = 1 ; 
    }
    cin>>k ; 
    for(int i = 0 ; i <k ; i++){
        int a ; 
        cin>>a ; 
        bad[a] = 1 ; 
        v.push_back(a) ; 
        Q.push({0 , a}) ; 
    }
    dijkstra() ; 
    cin>>q ; 
    while(q--){
        int a , b ; 
        cin>>a>>b ;
        if(a>b)swap(a , b) ;  
        if(mp[{a , b}]){
            cout<<min(d[a] , d[b])<<"\n";
            continue ; 
        }
        int l = 0 , r = 1e9  , ans =0 ; 
        while(l<=r){
            int mid = (l+r)/2 ; 
            t++ ; 
            B = b ; 
            limit = mid ; 
            dfs(a) ; 
            if(vis[b]==t && d[a] >=limit){
                l = mid + 1 ; 
                ans = mid ; 
            }
            else {
                r = mid  - 1; 
            }
        }
        cout<<ans<<"\n" ; 

    }
    return 0 ; 
}

Compilation message (stderr)

plan.cpp: In function 'int dfs(int)':
plan.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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