#666343 (C++17) No.1473 おでぶなおばけさん

提出ソース

結果

問題	No.1473 おでぶなおばけさん
ユーザー	tkmst201
提出日時	2021-06-13 09:32:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	74 ms / 2,000 ms
コード長	2,114 bytes
コンパイル時間	2,439 ms
コンパイル使用メモリ	215,236 KB
実行使用メモリ	11,136 KB
最終ジャッジ日時	2024-06-01 09:05:43
合計ジャッジ時間	6,535 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	70 ms 10,624 KB
testcase_03	AC	53 ms 9,088 KB
testcase_04	AC	36 ms 7,552 KB
testcase_05	AC	13 ms 5,376 KB
testcase_06	AC	57 ms 9,088 KB
testcase_07	AC	74 ms 11,136 KB
testcase_08	AC	74 ms 11,136 KB
testcase_09	AC	74 ms 11,136 KB
testcase_10	AC	41 ms 5,376 KB
testcase_11	AC	40 ms 5,376 KB
testcase_12	AC	39 ms 5,376 KB
testcase_13	AC	25 ms 5,376 KB
testcase_14	AC	19 ms 5,376 KB
testcase_15	AC	34 ms 5,376 KB
testcase_16	AC	38 ms 5,376 KB
testcase_17	AC	4 ms 5,376 KB
testcase_18	AC	7 ms 5,376 KB
testcase_19	AC	33 ms 5,376 KB
testcase_20	AC	44 ms 8,448 KB
testcase_21	AC	47 ms 6,784 KB
testcase_22	AC	49 ms 9,472 KB
testcase_23	AC	42 ms 8,960 KB
testcase_24	AC	41 ms 8,448 KB
testcase_25	AC	52 ms 9,216 KB
testcase_26	AC	55 ms 9,088 KB
testcase_27	AC	21 ms 5,376 KB
testcase_28	AC	64 ms 11,008 KB
testcase_29	AC	40 ms 6,944 KB
testcase_30	AC	46 ms 7,552 KB
testcase_31	AC	58 ms 11,008 KB
testcase_32	AC	46 ms 8,960 KB
testcase_33	AC	40 ms 8,192 KB
testcase_34	AC	23 ms 6,144 KB
testcase_35	AC	23 ms 5,632 KB
testcase_36	AC	39 ms 6,912 KB
testcase_37	AC	43 ms 8,704 KB
testcase_38	AC	10 ms 5,376 KB
testcase_39	AC	39 ms 5,376 KB
testcase_40	AC	39 ms 5,376 KB
testcase_41	AC	36 ms 5,376 KB
testcase_42	AC	36 ms 5,376 KB
testcase_43	AC	40 ms 8,448 KB
testcase_44	AC	39 ms 8,448 KB
testcase_45	AC	40 ms 8,320 KB
testcase_46	AC	51 ms 8,192 KB
testcase_47	AC	63 ms 9,216 KB
testcase_48	AC	58 ms 8,960 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = false;
//---------------------------------//

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/UnionFind.hpp
 */
struct UnionFind {
	using size_type = std::size_t;
	
private:
	size_type n;
	std::vector<int> dat;
	
public:
	explicit UnionFind(size_type n) : n(n), dat(n, -1) {}
	
	size_type size(size_type x) noexcept {
		assert(x < n);
		return -dat[find(x)];
	}
	
	size_type find(size_type x) noexcept {
		assert(x < n);
		if (dat[x] < 0) return x;
		return dat[x] = find(dat[x]);
	}
	
	void unite(size_type x, size_type y) noexcept {
		assert(x < n);
		assert(y < n);
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (dat[x] < dat[y]) std::swap(x, y);
		dat[y] += dat[x];
		dat[x] = y;
	}
	
	bool issame(size_type x, size_type y) noexcept {
		assert(x < n);
		assert(y < n);
		return find(x) == find(y);
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> g(N);
	UnionFind uf(N);
	vector<int> S(M), T(M), D(M);
	REP(i, M) scanf("%d %d %d", &S[i], &T[i], &D[i]), --S[i], --T[i];
	vector<int> ord(M);
	iota(ALL(ord), 0);
	sort(ALL(ord), [&](int i, int j) { return D[i] > D[j]; });
	int mx = 0;
	for (int i : ord) {
		if (uf.issame(0, N - 1) && mx > D[i]) break;
		uf.unite(S[i], T[i]);
		g[S[i]].emplace_back(T[i]);
		g[T[i]].emplace_back(S[i]);
		mx = D[i];
	}
	
	queue<int> que;
	vector<int> dist(N, INF);
	que.emplace(0);
	dist[0] = 0;
	while (!que.empty()) {
		auto u = que.front(); que.pop();
		for (int v : g[u]) if (chmin(dist[v], dist[u] + 1)) que.emplace(v);
	}
	cout << mx << " " << dist[N - 1] << endl;
}

yukicoder

結果

テストケース

ソースコード