Submission #857276

#	Time	Username	Problem	Language	Result	Execution time	Memory
857276		NaimSS	Evacuation plan (IZhO18_plan)	C++17	100 / 100	497 ms	42432 KiB

plan

#include <bits/stdc++.h>
#include <iostream>
// #define int long long
#define ld long double
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v)),v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
// std::mt19937_64 rng64((int) std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(
  
//  (int) std::chrono::steady_clock::now().time_since_epoch().count()
   1239010
);
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
//inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
    b%=m;
    ll ans = 1;
    for (; e; b = b * b % m, e /= 2)
        if (e & 1) ans = ans * b % m;
    return ans;
}
// debug:
template<class T>void print_vector(vector<T> &v){
    rep(i,0,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];
}
void dbg_out() {cerr << endl; }
template<typename Head, typename ... Tail> void dbg_out(Head H,Tail... T){
    cerr << ' ' << H;
    dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl
#else
#define dbg(...) 42
#endif
//

const int N = 100100;
int n,m;
int d[N];
vector<pii> g[N];

int p[N], ps[N], ar[N];
int f(int x){
	while(p[x]!=x)x=p[x];
	return x;
}
int H(int x){
	int r=0;
	while(p[x]!=x)x = p[x], r++;
	return r;
}
void join(int a,int b,int val){
	a = f(a),b=f(b);
	if(a==b)return;
	if(ps[a] > ps[b])swap(a,b);
	ps[b] += ps[a];
	p[a] = b;
	ar[a] = val;
}
int qry(int a,int b){
	int ha = H(a), hb = H(b);
	int res = 1e9;
	while(a!=b){
		if(ha > hb){
			res = min(res, ar[a]);
			a = p[a];
			ha--;
		}else{
			res = min(res, ar[b]), b = p[b], hb--;
		}
	}
	return res;
}

int32_t main(){
    fastio;
	cin >> n >> m;
	rep(i,0,m){
		int a,b,c;
		cin >> a >> b >> c;
		g[a].pb(pii(b,c));
		g[b].pb(pii(a,c));
	}
	rep(i,1,n+1)d[i] = 1e9;
	int k;
	cin >> k;
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	rep(i,0,k){
		int v;
		cin >> v;
		if(d[v]!=0){
			d[v] = 0;
			pq.push(pii(d[v] , v));
		}
	}
	while(!pq.empty()){
		auto [dd, v] = pq.top();
		pq.pop();
		if(dd != d[v])continue;
		for(auto [to,w] : g[v]){
			if(d[to] > d[v] + w){
				pq.push(pii(d[to] = d[v] + w , to));
			}
		}
	}

	rep(i,1,n+1){
		p[i] = i,ps[i] = 1;
	}
	vector<array<int,3>> ed;
	rep(i,1,n+1)for(auto [to,w] : g[i]){
		ed.pb({min(d[i], d[to]), i , to});
	}
	sort(all(ed));
	reverse(all(ed));
	for(auto [val,a,b] : ed){
		join(a,b,val);
	}
	int q;
	cin >> q;
	while(q--){
		int s,t;
		cin >> s >> t;
		cout << qry( s , t )<< endl;
	}

	// math -> gcd it all
    // Did you swap N,M? N=1?
}

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