Submission #783839

#	Time	Username	Problem	Language	Result	Execution time	Memory
783839		anton	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4053 ms	35556 KiB

plan

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

const int INF = (1LL<<61LL)-1LL;

int n, m;
vector<vector<pii>> adj;
int k;
vector<int> npp;
int q;
vector<pii> query;
vector<pii> cities;
vector<int> pos;
vector<int> next_pos;

vector<int> dsu;
vector<int> sz;

int getC(int a){
    int r =a;
    vector<int> p;
    while(dsu[r]!=-1){
        p.push_back(r);
        r =dsu[r];
    }
    for(auto e: p){
        dsu[e] = r;
    }
    return r;
}

void merge(int a, int b){
    a = getC(a);
    b= getC(b);
    if(a==b){
        return;
    }
    if(sz[b]>=sz[a]){
        dsu[b] = a;
        sz[b]+=sz[a];
    }
    else{
        dsu[a] =b;
        sz[a]+=sz[b];
    }
}

void run_step(int step){
    //cout<<"running "<<step<<endl;
    vector<pii> q_ordered;
    dsu.clear();
    dsu.resize(n, -1);
    sz.clear();
    sz.resize(n, 1);

    for(int i = 0; i<q; i++){
        q_ordered.push_back(pii(next_pos[i], i));
    }

    sort(q_ordered.begin(), q_ordered.end());
    int q_id= q-1;
    vector<bool> inserted(n, false);

    for(int c_id = n-1; c_id>=0; c_id--){
        int city = cities[c_id].second;
        int c_dist = cities[c_id].first;
        inserted[city] = true;
        for(auto e: adj[city]){
            if(inserted[e.first]){
                merge(e.first, city);
            }
        }

        while(q_id>=0 && (q_ordered[q_id].first<= c_dist && (c_id == 0|| q_ordered[q_id].first>cities[c_id-1].first))){
            int query_name = q_ordered[q_id].second;
            if(getC(query[query_name].first)== getC(query[query_name].second) && inserted[query[query_name].first] && inserted[query[query_name].second]){
                pos[query_name] = next_pos[query_name];
            }
            q_id--;
        }
    }

}

void run_all(){
    //cout<<"running "<<step<<endl;
    vector<pii> q_ordered;
    dsu.clear();
    dsu.resize(n, -1);
    sz.clear();
    sz.resize(n, 1);

    for(int i = 0; i<q; i++){
        q_ordered.push_back(pii(next_pos[i], i));
    }

    sort(q_ordered.begin(), q_ordered.end());
    int q_id= q-1;
    vector<bool> inserted(n, false);

    for(int c_id = n-1; c_id>=0; c_id--){
        int city = cities[c_id].second;
        int c_dist = cities[c_id].first;
        inserted[city] = true;
        for(auto e: adj[city]){
            if(inserted[e.first]){
                merge(e.first, city);
            }
        }
        

        for(int i = 0; i<q; i++){
            if(pos[i]==-1){
                int query_name = q_ordered[i].second;
                //cout<<"maybe "<<query_name<<endl;
                if(getC(query[query_name].first)== getC(query[query_name].second) && inserted[query[query_name].first] && inserted[query[query_name].second]){
                    pos[query_name] =c_dist;
                }
            }
        }
        
    }
}

signed main(){
    cin>>n>>m;

    adj.resize(n);
    for(int i = 0; i<m; i++){
        int a, b, w;
        cin>>a>>b>>w;
        a--;b--;
        adj[a].push_back(pii(b, w));
        adj[b].push_back(pii(a, w));
    }
    
    cities.resize(n);

    cin>>k;
    npp.resize(k);
    for(int i =0; i<k;i++){
        cin>>npp[i];
        npp[i]--;
    }

    vector<int> dist(n, INF);
    vector<bool> vis(n, false);
    priority_queue<pii> pq;
    for(int e: npp){
        pq.push(pii(0, e));
        dist[e] = 0;
    }

    while(pq.size()>0){
        auto cur =pq.top();
        pq.pop();
        swap(cur.first, cur.second);
        cur.second = -cur.second;
        //cout<<cur.first<<" "<<cur.second<<endl;

        if(dist[cur.first]== cur.second && !vis[cur.first]){
            vis[cur.first]= true;

            for(auto neig: adj[cur.first]){
                int potential = cur.second + neig.second;

                if(potential < dist[neig.first]){
                    dist[neig.first] = potential;
                    pq.push(pii(-potential, neig.first));
                }
            }
        }
    }


    for(int i = 0; i<n; i++){
        //cout<<"i: "<<i<<" "<<dist[i]<<endl;
        cities[i] = pii(dist[i], i);
    }

    sort(cities.begin(), cities.end());

    //cout<<INF<<endl;

    cin>>q;
    query.resize(q);
    pos.resize(q, -1);
    next_pos.resize(q, -1);

    for(int i = 0; i<q; i++){
        cin>>query[i].first>>query[i].second;
        query[i].first--;query[i].second--;
    }

    //cout<<"done reading"<<endl;

    /*for(int step = (1LL<<40LL); step>=1LL; step/=2LL){
        for(int i= 0; i<q; i++){
            next_pos[i] = pos[i]+step;
        }
        //cout<<"gonna run"<<endl;

        run_step(step);
    }*/

    run_all();

    for(int i = 0; i<q; i++){
        if(query[i].first != query[i].second){
            cout<<pos[i]<<endl;
        }
        else{
            cout<<dist[query[i].first]<<endl;
        }
    }
}

Compilation message (stderr)

plan.cpp: In function 'void run_all()':
plan.cpp:101:9: warning: unused variable 'q_id' [-Wunused-variable]
  101 |     int q_id= q-1;
      |         ^~~~

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