Submission #783784

#	Time	Username	Problem	Language	Result	Execution time	Memory
783784		anton	Evacuation plan (IZhO18_plan)	C++17	19 / 100	2376 ms	35348 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 i = 0; i<n; i++){
        auto e = cities[i];
        //cout<<"city "<<e.second<<endl;
        inserted[e.second] = true;
        for(auto n: adj[e.second]){
            if(inserted[n.first]){
                merge(e.second, n.first);
            }
        }

            while(q_id<q && q_ordered[q_id].first<=e.first &&  (i== n-1||q_ordered[q_id].first> cities[i+1].first)){
                //cout<<q_id<<endl;
                int cur_query = q_ordered[q_id].second;
                if(getC(query[cur_query].first) ==  getC(query[cur_query].second)){
                    pos[cur_query]= next_pos[cur_query];
                    //cout<<query[cur_query].first<<" "<<query[cur_query].second<<" ok "<<e.first<<endl;
                }
                q_id++;
            }
        ////cout<<"i "<<i<<endl;
    }
    //cout<<"done "<<endl;*/

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

}

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());

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

    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<<30LL); step>=1LL; step/=2LL){
        for(int i= 0; i<q; i++){
            next_pos[i] = pos[i]+step;
        }
        //cout<<"gonna run"<<endl;

        run_step(step);
    }

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

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