제출 #571406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571406		BackNoob	Evacuation plan (IZhO18_plan)	C++14	100 / 100	542 ms	97204 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 24211007;
const ll infll = 1e18 + 7;
const int base = 200;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

vector<pair<int, int>> query[mxN];
ll ans[mxN];

struct DSU{
	vector<int> lab;
	DSU(){}
	DSU(int _n){
		lab.resize(_n + 7, -1);
	}

	int root(int u) {return lab[u] < 0 ? u : lab[u] = root(lab[u]);}

	bool union_root(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u == v) return false;
		if(lab[u] > lab[v]) swap(u, v);
		lab[u] += lab[v];
		lab[v] = u;
		return true;
	}
} dsu;

int n;
int m;
int k;
int q;
bool spec[mxN];
vector<pair<int, int>> adj[mxN];
vector<pair<int, ll>> g[mxN];
ll dist[mxN];
pair<ll, int> f[mxN];
bool vis[mxN];
int par[mxN][LOG];
ll mx[mxN][LOG];
int depth[mxN];

void sp()
{
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	memset(dist, 0x3f, sizeof(dist));
	for(int i = 1; i <= n; i++) {
		if(spec[i] == true) {
			dist[i] = 0;
			pq.push({dist[i], i});
		}
	}

	while(!pq.empty()) {
		int u = pq.top().se;
		ll cur = pq.top().fi;
		pq.pop();

		if(cur != dist[u]) continue;

		for(auto it : adj[u]) {
			if(minimize(dist[it.fi], cur + it.se) == true) {
				pq.push({dist[it.fi], it.fi});
			}
		}
	}
}

void dfs_tree(int u, int p)
{
	for(auto it : g[u]) {
		int v = it.fi;
		ll c = it.se;
		if(v == p) continue;
		par[v][0] = u;
		mx[v][0] = c;
		depth[v] = depth[u] + 1;
		dfs_tree(v, u);
	}
}

ll getans(int u, int v)
{
	if(depth[u] < depth[v]) swap(u, v);

	ll res = infll; 
	for(int j = LOG - 1; j >= 0; j--)
		if(depth[par[u][j]] >= depth[v]) {
			minimize(res, mx[u][j]);
			u = par[u][j];
		}

	if(u == v) return res;

	for(int j = LOG - 1; j >= 0; j--) {
		if(par[u][j] != par[v][j]) {
			minimize(res, mx[u][j]);
			minimize(res, mx[v][j]);
			u = par[u][j];
			v = par[v][j];
		}
	}
	return min({res,  mx[u][0], mx[v][0]});
}

void solve()
{	
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].pb({v, c});
		adj[v].pb({u, c});
	}	

	cin >> k;
	for(int i = 1; i <= k; i++) {
		int u;
		cin >> u;
		spec[u] = true;
	}



	sp();

	for(int i = 1; i <= n; i++) f[i] = {dist[i], i};
	sort(f + 1, f + 1 + n);

	// for(int i = 1; i <= n; i++) cout << f[i].fi << ' ' << f[i].se << endl;
	
	memset(ans, -0x3f, sizeof(ans));
	dsu = DSU(n);
	for(int i = n; i >= 1; i--) {
		int j = i;
		while(j > 0 && f[i].fi == f[j].fi) --j;
		for(int k = j + 1; k <= i; k++) vis[f[k].se] = true;
		for(int k = j + 1; k <= i; k++) {
			int u = f[k].se;
			for(auto it : adj[u]) {
				if(vis[it.fi] == true) 
					if(dsu.union_root(u, it.fi) == true) {
						g[u].pb({it.fi, f[i].fi});
						g[it.fi].pb({u, f[i].fi});
					}
			}
		}
		i = j + 1;
	}

	dfs_tree(1, -1);
	par[1][0] = 1;
	mx[1][0] = infll;
	for(int j = 1; j < LOG; j++) {
		for(int i = 1; i <= n; i++) {
			par[i][j] = par[par[i][j - 1]][j - 1];
			mx[i][j] = min(mx[i][j - 1], mx[par[i][j - 1]][j - 1]);
		}
	}

	cin >> q;
	for(int i = 1; i <= q; i++) {
		int u, v;
		cin >> u >> v;
		cout << getans(u, v) << endl;
	}
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
		
    int tc = 1;
    // cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

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