Submission #210229

#	Time	Username	Problem	Language	Result	Execution time	Memory
210229		mohamedsobhi777	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1572 ms	112844 KiB

plan

#include<bits/stdc++.h> 

using namespace std ; 

const int N = 5e5 + 7 ; 

int n , m , k , q ; 
bool bad[N] , good[N] , viz[N];
int root ;
vector<pair<int , int > > adj[N] ;
vector<int> qrs[N] , tree[N]; 
priority_queue<pair<int , int > > Q; 
int d[N] , ans[N]; 
vector<int> v ; 
vector<pair<int , int > > prs ; 

struct DSU{

    vector<int> fat ; 

    void init(int n){
        fat.resize(n + 1 ) ; 
        for(int i = 0 ; i < n ; i++){
            fat[i] = i ; 
        }
    }
    int fin(int x){
        return fat[x] = (fat[x]==x?x:fin(fat[x])) ; 
    }

    void unio(int a, int b){
        int aa = fin(a) ;
        int bb = fin(b) ; 
        if(aa!=bb){
            fat[aa] = bb  ;
        }
    }


} d1 , d2;


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] ;

vector<pair<int , int > > node ; 

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 ; 
map<pair<int , int > , int > sol ; 

int cur ; 

void dfs_lca(int x , int p ){
    viz[x] = 1 ; 
    for(auto u : qrs[x]){
        if(viz[u] && mp[{x ,u}]==0){
            int lca = d2.fin(u) ; 
            mp[{x , u}] = mp[{u , x}] = 1 ; 
            sol[{x , u}] = sol[{u , x}] = d[lca] ;
        }
    }
    for(auto u : tree[x]){
        if(u==p)
            continue ; 
        dfs_lca(u ,x ) ; 
        d2.unio(u , x) ; 
    }
}

int main(){
    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}) ; 
    }
    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 ; 
    for(int i = 0 ; i < q ; i++){
        int a, b ; 
        cin>>a>>b ; 
        prs.push_back({a ,b }) ; 
        qrs[a].push_back(b) ; 
        qrs[b].push_back(a) ; 
    }
    
    for(int i = 1 ; i <=n ; i++){
        node.push_back({-d[i] , i}) ; 
    }
    sort(node.begin() , node.end()) ;
    d1.init(N) ; 
    for(auto u : node){
        int nod = u.second ; 
        int val = -u.first ; 
        int home = d1.fin(nod) ;
        good[nod] = 1 ;  
        ans[home] = val ; 

        for(auto it : adj[nod]){
            if(good[it.first]){
                int fn = d1.fin(it.first) ; 
                if(fn!=home){
                    if(ans[fn] < ans[home])
                    d1.unio(home , fn) ; 
                    else 
                    d1.unio(fn , home) ;
                    tree[fn].push_back(home) ; 
                    tree[home].push_back(fn) ;
                }

            }
        }
        root = nod ; 
    }
    d2.init(N) ; 
    dfs_lca(root , root) ; 
    for(int i = 0 ; i < q ; i++){
        cout<<sol[prs[i]]<<"\n";
    }
    return 0 ; 
}

Compilation message (stderr)

plan.cpp: In function 'int dfs(int)':
plan.cpp:76: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: 46 / 46