Submission #367207

#	Time	Username	Problem	Language	Result	Execution time	Memory
367207		nicolaalexandra	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1357 ms	89280 KiB

plan

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

struct muchie{
    int x,y,cost;
};
vector <muchie> mch;

vector <pair<int,int> > L[DIM],edg[DIM];
priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h;
int E[DIM*4],p[DIM*4],level[DIM],t[DIM],first[DIM],dist[DIM],v[DIM];
pair <int,int> rmq[21][DIM*4],dp[21][DIM];
int n,m,q,x,y,cost,i,j,k,cnt;

inline int cmp (muchie a, muchie b){
    return a.cost > b.cost;
}

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

void dfs (int nod, int tata){
    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[tata];
    for (auto it : edg[nod]){
        int vecin = it.first, cost = it.second;
        if (vecin != tata){
            dp[0][vecin] = make_pair(cost,nod);
            dfs (vecin,nod);
            E[++k] = nod;
        }}}

int get_lca (int x, int y){
    int pozx = first[x], pozy = first[y];
    if (pozx > pozy)
        swap (pozx,pozy);
    int nr = p[pozy-pozx+1];
    pair <int,int> sol = min (rmq[nr][pozx],rmq[nr][pozy-(1<<nr)+1]);
    return E[sol.second];
}

int get_min (int x, int lca){

    int sol = INF;
    for (int i=20;i>=0;i--){
        int y = dp[i][x].second;
        if (level[y] < level[lca])
            continue;

        sol = min (sol,dp[i][x].first);
        x = y;
    }
    return sol;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
    }

    for (i=1;i<=n;i++)
        dist[i] = INF;

    cin>>cnt;
    for (i=1;i<=cnt;i++){
        cin>>v[i];
        h.push(make_pair(0,v[i]));
        dist[v[i]] = 0;
    }

    while (!h.empty()){
        int nod = h.top().second;
        int cost = h.top().first;
        h.pop();
        if (dist[nod] != cost)
            continue;
        for (auto it : L[nod]){
            int vecin = it.first, new_cost = it.second;
            if (dist[nod] + new_cost < dist[vecin]){
                dist[vecin] = dist[nod] + new_cost;
                h.push(make_pair(dist[vecin],vecin));
            }}}

    /*cin>>q;
    for (i=1;i<=q;i++)
        cin>>qry[i].first>>qry[i].second;*/

    for (i=1;i<=n;i++){
        for (auto it : L[i]){
            int vecin = it.first;
            mch.push_back({i,vecin,min(dist[i],dist[vecin])});
        }
    }

    sort (mch.begin(),mch.end(),cmp);
    memset (t,-1,sizeof t);

    for (auto it : mch){
        int x = it.x, y = it.y;
        int radx = get_rad(x), rady = get_rad(y);
        if (radx != rady){
            //cout<<x<<" "<<y<<" "<<it.cost<<"\n";
            edg[x].push_back(make_pair(y,it.cost));
            edg[y].push_back(make_pair(x,it.cost));

            if (t[radx] > t[rady])
                swap (radx,rady);
            t[radx] += t[rady];
            t[rady] = radx;
        }
    }

    dfs (1,0);

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);

    for (i=1;(1<<i)<=k;i++)
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++){
            dp[i][j].second = dp[i-1][dp[i-1][j].second].second;
            dp[i][j].first = min (dp[i-1][j].first,dp[i-1][dp[i-1][j].second].first);
        }

    cin>>q;
    for (i=1;i<=q;i++){
        cin>>x>>y;
        int lca = get_lca (x,y);

        cout<<min(get_min(x,lca),get_min(y,lca))<<"\n";
    }

    return 0;
}

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