Submission #210230

#	Time	Username	Problem	Language	Result	Execution time	Memory
210230		mohamedsobhi777	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1853 ms	103464 KiB

plan

#include<bits/stdc++.h> 

using namespace std ; 

const int N = 5e5 + 7 ; 

/*
    idea: break the problem into smaller subproblems 
    we need a path from A to B, avoiding bad nodes as much as we can
    first we need to know for each node the closest bad node to it(let's call it C[node]) which can be done if we run a dijkstra from each bad node simultaneously
    now the problem turns to the following
    find a path from A to B such that the the min of C[x] for each node x on the path is maximum
    one possible way to do that is to process each node after sorting them decresingly by C[i]
    when processing a node, we mark it as good, and look for its good neighbours to link them to it using DSU
    after processing each node, the answer to query {u , v} such that u and v is in the same component is min of all C[i] of nodes processed so far,
    if they are not in the same component we continue processing other nodes, so it make sense that we look for the first time nodes {u , v} were in the same
    component, which is the same as their lca if we root the tree at the last node we conunter, so the answer to query {u , v} = C[lca(u , v)] of the DSU tree


    submission : https://oj.uz/submission/210229


*/

int n , m , k , q ; 
vector<pair<int , int > > adj[N] ;
vector<pair<int , int > > queries ; 


bool good[N] , viz[N];
int root ;
vector<int> qrs[N] , tree[N]; 

// this is DSU
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;

//using dijkstra to calculate the closest bad node 
priority_queue<pair<int , int > > Q; 
int C[N]; 

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

vector<pair<int , int > > node ; 
    
map<pair<int , int > , bool > mp ; 
map<pair<int , int > , int > sol ; 


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}] = C[lca] ;
        }
    }
    for(auto u : tree[x]){
        if(u==p)
            continue ; 
        dfs_lca(u ,x ) ; 
        d2.unio(u , x) ; 
    }
}

int main(){
    memset(C , -1 , sizeof C) ; 
    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}) ; 
    }
    
    //calculating the distance between each node to the nearest bad node
    cin>>k ; 
    for(int i = 0 ; i <k ; i++){
        int a ; cin>>a ; 
        C[a] =0 ;
        Q.push({0 , a}) ; 
    }
    dijkstra() ; 
    //
    
    cin>>q ; 
    for(int i = 0 ; i < q ; i++){
        int a, b ; 
        cin>>a>>b ; 
        queries.push_back({a ,b });
        qrs[a].push_back(b) ; 
        qrs[b].push_back(a) ; 
    }

    //sorting the nodes decresingly by C[i]
    for(int i = 1 ; i <=n ; i++){   
        node.push_back({-C[i] , i}) ; 
    }
    sort(node.begin() , node.end()) ;
    
    //process each node, mark it as good, and link it to its good neighbours
    d1.init(N) ; 
    for(auto u : node){
        int nod = u.second ; 
        int home = d1.fin(nod) ;
        good[nod] = 1 ;  

        for(auto it : adj[nod]){
            if(good[it.first]){
                int fn = d1.fin(it.first) ; 
                if(fn!=home){
                    if(C[fn] < C[home])d1.unio(home , fn) ; 
                    else  d1.unio(fn , home) ;
                    //make a tree of the dsu components 
                    tree[fn].push_back(home) ; 
                    tree[home].push_back(fn) ;
                }

            }
        }
        root = nod ; 
    }

    //calculate the LCA for each query using DSU offline
    d2.init(N) ; 
    dfs_lca(root , root) ; 

    //printing the answer
    for(int i = 0 ; i < q ; i++){
        cout<<sol[queries[i]]<<"\n";
    }
    return 0 ; 
}

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