Submission #1268655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268655		tminh	Evacuation plan (IZhO18_plan)	C++20	100 / 100	288 ms	68036 KiB

plan

#include "bits/stdc++.h"
using namespace std;

#define task ""
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define vall(a) (a).begin(), (a).end()
#define sze(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>


#define ep emplace_back
#define pb push_back
#define pf push_front


const ll mod = 1e9 + 7;
const int N = 5e5 + 5;
const ll oo = 1e18;
const int base = 19;

bool START;
// so lan doc sol roi moi biet lam :


int n, m, Q, k;
ll d[N];
vector<pll> adj[N], e[N];


struct DSU {
	int par[N], sz[N];
	void init() {
		for (int i = 1; i <= n; ++i) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	int find(int v) {
		return v == par[v] ? v : par[v] = find(par[v]);
	}
	bool merge(int a, int b) {
		a = find(a);
		b = find(b);
		if (a != b) {
			if (sz[a] < sz[b]) swap(a, b);
			par[b] = a;
			sz[a] += sz[b];
			return true;
		}
		return false;
	}
} dsu;


struct node {
	int u, v; ll c;
	node(int u_ = 0, int v_ = 0, ll c_ = 0) : u(u_), v(v_), c(c_) {}
	bool operator<(const node &other) const {
		return c > other.c;
	}
} E[N];

priority_queue<pll, vector<pll>, greater<pll>> q;
void dijkstra() {
	for (int i = 1; i <= n; ++i) d[i] = oo;
	for (int i = 1; i <= k; ++i) {
		int s; cin >> s;
		d[s] = 0;
		q.push(make_pair(d[s], s));
	}
	while(!q.empty()) {
		auto[c, u] = q.top();
		q.pop();
		if (d[u] != c) continue;
		
		for (auto[v, w] : adj[u]) {
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				q.push(make_pair(d[v], v));
			}
		}
	}
}

int h[N], par[N][base];
ll Min[N][base];
void dfs(int u) {
	for (auto [v, w] : e[u]) {
		if (v == par[u][0]) continue;
		h[v] = h[u] + 1;
		par[v][0] = u;
		Min[v][0] = w;
		for (int i = 1; i < base; ++i) {
			par[v][i] = par[par[v][i - 1]][i - 1];
			Min[v][i] = min(Min[v][i - 1], Min[par[v][i - 1]][i - 1]); 
		}
		dfs(v);
	}
}

int get(int u, int v) {
	ll ansmin = oo;
	if (h[u] < h[v]) swap(u, v);
	int k = h[u] - h[v];
	
	
	for (int i = 0; (1 << i) <= k; ++i) {
		if ((k >> i) & 1) {
			ansmin = min(ansmin, Min[u][i]);
			u = par[u][i];
		}
	}
	if (u == v) return ansmin;
	for (int i = base - 1; i >= 0; --i) {
		if (par[u][i] != par[v][i]) {
			ansmin = min({ansmin, Min[u][i], Min[v][i]});
			u = par[u][i];
			v = par[v][i];
		}
	}
	return min({ansmin, Min[v][0], Min[u][0]});
}


inline void solve() {
	dijkstra();
	for (int i = 1; i <= m; ++i) E[i].c = min(d[E[i].u], d[E[i].v]);
	sort(E + 1, E + 1 + m);
	
	dsu.init();
	for (int i = 1; i <= m; ++i) {
		auto[u, v, c] = E[i];
		if (dsu.merge(u, v)) {
			e[u].ep(v, c);
			e[v].ep(u, c);
		}
	}
	par[1][0] = 1;
	Min[1][0] = oo;
	dfs(1);
	cin >> Q;
	while(Q--) {
		int u, v;
		cin >> u >> v;
		cout << get(u, v) << endl;
	}
	
	
}


inline void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
    	int u, v, c;
    	cin >> u >> v >> c;
    	adj[u].ep(v, c);
    	adj[v].ep(u, c);
    	E[i] = node(u, v, 0);
    }
    cin >> k;
    return solve();
}
bool END;

int main() {
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    input();
    
    
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
    cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n";
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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