Submission #378588

#	Time	Username	Problem	Language	Result	Execution time	Memory
378588		casperwang	Evacuation plan (IZhO18_plan)	C++14	19 / 100	573 ms	60756 KiB

plan

#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define All(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 100000;
const int INF = 1e18;
int n, m, k, q;
int a, b, c;
vector <pii> path[MAXN+1];
vector <int> arr[MAXN+1];
vector <pii> qry;
int v[MAXN+1];
int dsu[MAXN+1];
int mmin[MAXN+1];
int ans[MAXN];
priority_queue <pii, vector<pii>, greater<pii>> nxt;
vector <tuple<int,int,int>> E;

void init() {
	for (int i = 1; i <= n; i++)
		v[i] = INF;
	for (int i = 1; i <= n; i++)
		dsu[i] = i;
}

void dijkstra() {
	while (nxt.size()) {
		auto [d, now] = nxt.top();
		nxt.pop();
		if (d > v[now]) continue;
		for (auto [i, c] : path[now]) {
			if (v[i] > d + c) {
				v[i] = d + c;
				nxt.emplace(v[i], i);
			}
		}
	}
}

int fnd(int a) {
	return dsu[a] == a ? a : dsu[a] = fnd(dsu[a]);
}

void Merge(int a, int b) {
	a = fnd(a), b = fnd(b);
	if (a == b) return;
	if (arr[a].size() < arr[b].size()) {
		dsu[a] = b;
		mmin[b] = min(mmin[b], mmin[a]);
		vector <int> tmp;
		for (int i : arr[a]) {
			auto [x, y] = qry[i];
			if (fnd(x) == fnd(y)) {
				ans[i] = mmin[b];
			} else {
				tmp.pb(i);
			}
		}
		for (int i : tmp) arr[b].pb(i);
	} else {
		dsu[b] = a;
		mmin[a] = min(mmin[a], mmin[b]);
		vector <int> tmp;
		for (int i : arr[b]) {
			auto [x, y] = qry[i];
			if (fnd(x) == fnd(y)) {
				ans[i] = mmin[a];
			} else {
				tmp.pb(i);
			}
		}
		for (int i : tmp) arr[a].pb(i);
	}
}

void solve() {
	for (int i = 1; i <= n; i++) {
		mmin[i] = v[i];
		for (auto [j, c] : path[i]) {
			if (v[i] < v[j]) continue;
			E.pb(v[j], i, j);
		}
	}
	sort(All(E), greater<tuple<int,int,int>>());
	for (int i = 0; i < E.size(); i++) {
		auto [o, a, b] = E[i];
		Merge(a, b);
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		path[a].pb(b, c);
		path[b].pb(a, c);
	}
	init();
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> a;
		v[a] = 0;
		nxt.emplace(v[a], a);
	}
	dijkstra();
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		arr[a].pb(i);
		arr[b].pb(i);
		qry.pb(a, b);
	}
	solve();
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra()':
plan.cpp:37:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |   auto [d, now] = nxt.top();
      |        ^
plan.cpp:40:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for (auto [i, c] : path[now]) {
      |             ^
plan.cpp: In function 'void Merge(long long int, long long int)':
plan.cpp:61:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |    auto [x, y] = qry[i];
      |         ^
plan.cpp:74:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |    auto [x, y] = qry[i];
      |         ^
plan.cpp: In function 'void solve()':
plan.cpp:88:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |   for (auto [j, c] : path[i]) {
      |             ^
plan.cpp:94:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for (int i = 0; i < E.size(); i++) {
      |                  ~~^~~~~~~~~~
plan.cpp:95:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |   auto [o, a, b] = E[i];
      |        ^

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