제출 #378593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378593		Kevin_Zhang_TW	Evacuation plan (IZhO18_plan)	C++17	100 / 100	605 ms	33888 KiB

plan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(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 debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 100010, inf = 1e9;

vector<pair<int,int>> edge[MAX_N], allq[MAX_N];

template<class T> void join (vector<T> &a, vector<T> &b) { if (a.size() < b.size()) swap(a, b); a.insert(end(a), AI(b)); b.clear(); }

int dis[MAX_N], res[MAX_N];
bool vis[MAX_N];

int n, m, q;

struct dsu {
	vector<int> g;
	vector<vector<tuple<int,int,int>>> qry;
	dsu(int n) {
		g.resize(n+1); iota(AI(g), 0);
		qry.resize(n+1);
		for (int i = 1;i <= n;++i) {
			for (auto [b, id] : allq[i])
				qry[i].pb(i, b, id);
		}
	}
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	void M(int a, int b, int cost) {
		a = F(a), b = F(b);
		if (a == b) return;
		if (qry[a].size() < qry[b].size()) swap(a, b);
		g[b] = a;
		for (auto [v, u, ind] : qry[b]) {
			if (res[ind]) continue;
			if (F(v) == F(u))
				res[ind] = cost;
			else
				qry[a].pb(v, u, ind);
		}
		qry[b].clear();
	}
};

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int a, b, w, i = 0;i < m;++i) {
		cin >> a >> b >> w;
		edge[a].pb(b, w), edge[b].pb(a, w);
	}

	fill(dis, dis + 1 + n, inf);

	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

	auto upd = [&](int x, int d) {
		if (chmin(dis[x], d))
			pq.emplace(d, x);
	};

	int k;

	cin >> k;

	for (int x, i = 0;i < k;++i) {
		cin >> x ;
		upd(x, 0);
	}

	cin >> q;

	for (int s, t, i = 0;i < q;++i) {
		cin >> s >> t;
		allq[s].pb(t, i);
		allq[t].pb(s, i);
	}

	while (pq.size()) {
		auto [d, x] = pq.top(); pq.pop();
		if (vis[x]) continue; vis[x] = true;
		for (auto [u, w] : edge[x])
			upd(u, w + d);
	}

	vector<int> od(n); iota(AI(od), 1);

	sort(AI(od), [&](int x, int y) {
			return dis[x] > dis[y];
			});

	dsu D(n + 10);

	for (int x : od) {
		DE(x, dis[x]);
		for (auto [u, _] : edge[x])
			if (dis[u] >= dis[x]) {
				DE(x, u);
				D.M(x, u, dis[x]);
			}
	}

	for (int i = 0;i < q;++i)
		cout << res[i] << '\n';

}

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int32_t main()':
plan.cpp:93:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   93 |   if (vis[x]) continue; vis[x] = true;
      |   ^~
plan.cpp:93:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   93 |   if (vis[x]) continue; vis[x] = true;
      |                         ^~~
plan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
plan.cpp:107:3: note: in expansion of macro 'DE'
  107 |   DE(x, dis[x]);
      |   ^~
plan.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
plan.cpp:110:5: note: in expansion of macro 'DE'
  110 |     DE(x, u);
      |     ^~

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