제출 #378619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378619		casperwang	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4009 ms	61480 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;
	vector <int> tmp;
	for (int i : arr[a]) {
		auto [x, y] = qry[i];
		if (fnd(x) + fnd(y) == a + b) {
			ans[i] = min(mmin[a], mmin[b]);
		} else {
			tmp.pb(i);
		}
	}
	arr[a] = tmp; tmp.clear();
	for (int i : arr[b]) {
		auto [x, y] = qry[i];
		if (fnd(x) + fnd(y) == a + b) {
			ans[i] = min(mmin[a], mmin[b]);
		} else {
			tmp.pb(i);
		}
	}
	arr[b] = tmp; tmp.clear();
	if (arr[a].size() < arr[b].size()) {
		dsu[a] = b;
		mmin[b] = min(mmin[b], mmin[a]);
		for (int i : arr[a]) arr[b].pb(i);
	} else {
		dsu[b] = a;
		mmin[a] = min(mmin[a], mmin[b]);
		for (int i : arr[b]) 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(0, 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';
	}
}

컴파일 시 표준 에러 (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:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   auto [x, y] = qry[i];
      |        ^
plan.cpp:67:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |   auto [x, y] = qry[i];
      |        ^
plan.cpp: In function 'void solve()':
plan.cpp:89:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |   for (auto [j, c] : path[i]) {
      |             ^
plan.cpp:95: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]
   95 |  for (int i = 0; i < E.size(); i++) {
      |                  ~~^~~~~~~~~~
plan.cpp:96:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   auto [o, a, b] = E[i];
      |        ^

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