Submission #378608

#	Time	Username	Problem	Language	Result	Execution time	Memory
378608		cheissmart	Evacuation plan (IZhO18_plan)	C++14	100 / 100	771 ms	57020 KiB

plan

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;

V<pi> G[N];
vi nodes;
int d[N], pos[N];
int ans[N];
int p[N], sz[N];

int find(int u) {
	return p[u] == u ? u : find(p[u]);
}

V<pair<int*, int>> his;

void SET(int& a, int b) {
	his.EB(&a, a);
	a = b;
}

void unite(int x, int y) {
	int rx = find(x), ry = find(y);
	if(rx == ry) return;
	if(sz[rx] > sz[ry]) swap(rx, ry);
	SET(p[rx], ry);
	SET(sz[ry], sz[rx] + sz[ry]);
}

void backto(int tm) {
	while(his.size() > tm) {
		*(his.back().F) = his.back().S;
		his.pop_back();
	}
}

void BS(V<array<int, 3>> qq, int l, int r) {
	auto connect = [&] (int u) {
		for(pi p:G[u]) {
			int v = p.F;
			if(pos[v] < pos[u])
				unite(u, v);
		} 
	};
	if(r - l == 1) {
		connect(nodes[l]);
		for(auto p:qq) {
			assert(find(p[0]) == find(p[1]));
			ans[p[2]] = d[nodes[l]];
		}
		return;
	}
	int m = (l + r) / 2;
	int tm = his.size();
	for(int i = l; i < m; i++)
		connect(nodes[i]);
	V<array<int, 3>> ql, qr;
	for(auto p:qq) {
		if(find(p[0]) == find(p[1]))
			ql.PB(p);
		else 
			qr.PB(p);
	}
	backto(tm);
	BS(ql, l, m);
	BS(qr, m, r);
}

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].EB(v, w);
		G[v].EB(u, w);
	}
	int s = 0, k;
	cin >> k;
	for(int i = 0; i < k; i++) {
		int u;
		cin >> u;
		G[s].EB(u, 0);
	}

	memset(d, 0x3f, sizeof d);
	priority_queue<pi, V<pi>, greater<pi>> pq;
	d[s] = 0;
	pq.push({d[s], s});
	while(pq.size()) {
		pi p = pq.top(); pq.pop();
		int u = p.S;
		if(d[u] < p.F) continue;
		for(pi e:G[u]) {
			int v = e.F, w = e.S;
			if(d[u] + w < d[v]) {
				d[v] = d[u] + w;
				pq.push({d[v], v});
			}
		}
	}

	int q;
	cin >> q;
	V<array<int, 3>> qq(q);
	for(int i = 0; i < q; i++) {
		cin >> qq[i][0] >> qq[i][1];
		qq[i][2] = i;
	}
	nodes = vi(n);
	iota(ALL(nodes), 1);
	sort(ALL(nodes), [&] (int u, int v) {
		return d[u] > d[v];
	});
	for(int i = 0; i < n; i++)
		pos[nodes[i]] = i;
	BS(qq, 0, n);
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
	
}

Compilation message (stderr)

plan.cpp: In function 'void backto(int)':
plan.cpp:46:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |  while(his.size() > tm) {
      |        ~~~~~~~~~~~^~~~

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