Submission #783899

#	Time	Username	Problem	Language	Result	Execution time	Memory
783899		anton	Evacuation plan (IZhO18_plan)	C++17	100 / 100	3474 ms	48304 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 p;

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

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

map<int, int> small;
vector<int> large;

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){
    int na = getC(a);
    int nb= getC(b);
    if(na==nb){
        return;
    }
    if(sz[nb]>=sz[na]){
        dsu[na] = nb;
        sz[na]+=sz[nb];
    }
    else{
        dsu[nb] =na;
        sz[nb]+=sz[na];
    }
}

void run_step(int step){
    dsu.clear();
    dsu.resize(n, -1);
    sz.clear();
    sz.resize(n, 1);

    vector<bool> inserted(n, false);

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

        for(auto req: next_pos[i]){
            if(getC(query[req].first)==getC(query[req].second)){
                pos[req] = i;
            }
        }
    }

}

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

    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;
        small.insert(pii(dist[i], -1));
    }

    int id=  0;
    p = small.size();
    cities.resize(p);

    for(pii e: small){
        small[e.first] = id;
        id++;
        large.push_back(e.first);
    }

    for(int i = 0; i<n; i++){
        cities[small[dist[i]]].push_back(i);
    }

    //cout<<INF<<endl;

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

    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){
        next_pos.clear();
        next_pos.resize(p);
        
        for(int i= 0; i<q; i++){
            if(pos[i]+step<p){
                next_pos[pos[i]+step].push_back(i);
            }
        }
        //cout<<"gonna run"<<endl;

        run_step(step);
    }

    //run_all();

    for(int i = 0; i<q; i++){
        cout<<large[pos[i]]<<endl;
        
    }
}

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