Submission #46596

#	Time	Username	Problem	Language	Result	Execution time	Memory
46596		ulna	Evacuation plan (IZhO18_plan)	C++11	100 / 100	597 ms	24724 KiB

plan

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

// why am I so weak

int n, m;
int d[100055];

typedef pair<int, int> P;

#define ft first
#define sd second

vector<P> g[100055], ng[100055];

int par[100055], _rank[100055];
bool used[100055];
int depth[100055], val[100055];

inline void add_edge(int from, int to, int cost) {
	g[from].push_back(P(to, cost));
}
int fin(int x) {
	if (par[x] == x) return x;
	return fin(par[x]);
}
void unite(int x, int y, int val) {
	x = fin(x), y = fin(y);

	if (x == y) return;
	if (_rank[x] > _rank[y]) swap(x, y);
	
	par[x] = y;
	ng[y].push_back(P(x, val));

	if (_rank[x] == _rank[y]) _rank[y]++;
}
void dfs(int v, int par = -1, int d = 0) {
	depth[v] = d;

	for (auto u : ng[v]) if (u.ft != par) {
		val[u.ft] = u.sd;
		dfs(u.ft, v, d + 1);
	}
}
int main() {
	scanf("%d %d", &n, &m);

	while (m--) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		x--, y--;
		
		add_edge(x, y, z);
		add_edge(y, x, z);
	}

	priority_queue<P, vector<P>, greater<P> > pq;
	memset(d, 63, sizeof(d));

	int k;
	scanf("%d", &k);

	while (k--) {
		int x;
		scanf("%d", &x);
		x--;

		d[x] = 0;
		pq.push(P(0, x));
	}

	while (!pq.empty()) {
		int v = pq.top().sd; pq.pop();

		if (used[v]) continue;

		used[v] = true;

		for (auto p : g[v]) if (d[p.ft] > d[v] + p.sd) {
			d[p.ft] = d[v] + p.sd;
			pq.push(P(d[p.ft], p.ft));
		}
	}

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	memset(used, false, sizeof(used));

	vector<int> vec(n);

	for (int i = 0; i < n; i++) vec[i] = i;

	sort(vec.begin(), vec.end(), [&] (int u, int v) {
		return d[u] > d[v];
	});

	for (auto u : vec) {
		used[u] = true;

		for (auto p : g[u]) if (used[p.ft]) {
			unite(u, p.ft, d[u]);
		}
	}	

	dfs(fin(0), -1, 0);

	int q;
	scanf("%d", &q);

	while (q--) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--, y--;

		int res = INT_MAX;

		while (depth[x] > depth[y]) {
			res = min(res, val[x]);
			x = par[x];
		}

		while (depth[y] > depth[x]) {
			res = min(res, val[y]);
			y = par[y];
		}

		while (x != y) {
			res = min(res, min(val[x], val[y]));
			x = par[x], y = par[y];
		}

		printf("%d\n", res);
	}

	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
plan.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

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