Submission #69204

#	Time	Username	Problem	Language	Result	Execution time	Memory
69204		istlemin	Evacuation plan (IZhO18_plan)	C++14	23 / 100	2509 ms	84532 KiB

plan

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

class UnionFind{
public:
	vi p,r;
	UnionFind(ll n){
        p.resize(n);
        rep(i,0,n) p[i] = i;
        r.resize(n,1);
	}

    ll find(ll a){
		return p[a]==a?a:p[a]=find(p[a]);
    }

    void join(ll a,ll b){
        a = find(a);
        b = find(b);

        if(r[a]>r[b]){
            p[b] = a;
        } else if(r[b]>r[a]){
			p[a] = b;
        } else {
            p[a] = b;
            r[b]++;
        }
    }
};

ll n,k;
vector<vector<pii>> ge;
vi g;

vi dist;

void getDists(){
	dist.resize(n,-1);
    set<pii> q;
    rep(i,0,k) q.emplace(0,g[i]);
    while(q.size()){
        ll v = q.begin()->second;
        ll d = q.begin()->first;
        q.erase(q.begin());
		if(dist[v]!=-1) continue;
		dist[v] = d;

		rep(i,0,ge[v].size()){
			q.emplace(d+ge[v][i].second,ge[v][i].first);
		}
    }
}

vector<vector<pii>> e;

void makeTree(){
    vector<tuple<ll,ll,ll> > edges;
    rep(i,0,n){
		rep(j,0,ge[i].size()){
			edges.emplace_back(min(dist[ge[i][j].first],dist[i]),i,ge[i][j].first);
		}
    }
    sort(all(edges));
    reverse(all(edges));

    UnionFind uf(n);
    e.resize(n);
    rep(i,0,edges.size()){
		ll a,b,w;
		tie(w,a,b) = edges[i];
        if(uf.find(a)!=uf.find(b)){
            uf.join(a,b);
			e[a].emplace_back(b,w);
			e[b].emplace_back(a,w);
        }
    }
}

class LCA {
public:
    vi levels;
    vector<vector<pii> > jump;

	LCA(){
		jump.resize(30,vector<pii>(n));
        levels.resize(n);
        dfs(0,0,0,1e18);

        rep(i,1,30){
			rep(j,0,n){
				jump[i][j].first = jump[i-1][jump[i-1][j].first].first;
				jump[i][j].second = min(jump[i-1][j].second,jump[i-1][jump[i-1][j].first].second);
			}
        }
	}

    void dfs(ll v,ll last,ll level,ll w){
        jump[0][v] = {last,w};
        levels[v] = level;
		rep(i,0,e[v].size()){
			if(e[v][i].first==last) continue;
			dfs(e[v][i].first,v,level+1,e[v][i].second);
		}
    }

    ll getMin(ll a,ll b){
        ll mn = 1e18;
        if(levels[a]<levels[b]) swap(a,b);
        for(int i = 29; i>=0;--i){
            if(levels[jump[i][a].first]>=levels[b]){
				mn = min(mn,jump[i][a].second);
				a = jump[i][a].first;
            }
        }
        assert(levels[a]==levels[b]);
        if(a==b) return mn;

        for(int i = 29; i>=0;--i){
            if(jump[i][a].first!=jump[i][a].first){
				mn = min(mn,jump[i][a].second);
				a = jump[i][a].first;
				mn = min(mn,jump[i][b].second);
				b = jump[i][b].first;
            }
        }
        //assert(a!=b);
		mn = min(mn,jump[0][a].second);
		a = jump[0][a].first;
		mn = min(mn,jump[0][b].second);
		b = jump[0][b].first;
		//assert(a==b);
		return mn;



    }
};

int main(){
	cin.sync_with_stdio(false);
    ll m;
    cin>>n>>m;
    ge.resize(n);
    rep(i,0,m){
		ll a,b,w;
		cin>>a>>b>>w;
		--a;--b;
        ge[a].emplace_back(b,w);
        ge[b].emplace_back(a,w);
    }
    cin>>k;
    g.resize(k);
    rep(i,0,k) {
		cin>>g[i];
		--g[i];
	}
	getDists();
    //rep(i,0,n) cout<<i+1<<": "<<dist[i]<<endl;
	makeTree();
	/*cout<<"tree"<<endl;
    rep(i,0,n){
		cout<<i+1<<": ";
		rep(j,0,e[i].size()){
			cout<<e[i][j].first+1<<" ";
		}
		cout<<endl;
    }*/

    LCA* lca = new LCA();

    ll q;
    cin>>q;
    rep(i,0,q){
		ll a,b;
		cin>>a>>b;
		--a; --b;
        cout<<lca->getMin(a,b)<<endl;
    }
    _Exit(0);
}

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