#615815 (C++17) No.1382 Travel in Mitaru city

提出ソース

結果

問題	No.1382 Travel in Mitaru city
ユーザー	tkmst201
提出日時	2021-02-10 12:45:40
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	1,894 bytes
コンパイル時間	2,409 ms
コンパイル使用メモリ	211,780 KB
実行使用メモリ	10,516 KB
最終ジャッジ日時	2024-07-07 23:14:46
合計ジャッジ時間	8,027 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	WA	-
testcase_07	AC	21 ms 6,940 KB
testcase_08	WA	-
testcase_09	AC	27 ms 6,940 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	57 ms 9,728 KB
testcase_28	AC	57 ms 9,600 KB
testcase_29	AC	57 ms 9,600 KB
testcase_30	AC	56 ms 9,600 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	37 ms 8,960 KB
testcase_37	AC	7 ms 6,944 KB
testcase_38	AC	41 ms 9,472 KB
testcase_39	AC	13 ms 6,944 KB
testcase_40	AC	33 ms 8,064 KB
testcase_41	AC	38 ms 8,576 KB
testcase_42	AC	45 ms 9,600 KB
testcase_43	AC	39 ms 8,832 KB
testcase_44	AC	18 ms 6,940 KB
testcase_45	AC	36 ms 8,192 KB
testcase_46	WA	-
testcase_47	WA	-
testcase_48	AC	31 ms 7,808 KB
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	AC	3 ms 6,944 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	7 ms 6,940 KB
testcase_64	AC	3 ms 6,944 KB
testcase_65	AC	2 ms 6,940 KB
testcase_66	AC	2 ms 6,940 KB
testcase_67	AC	3 ms 6,944 KB
testcase_68	AC	3 ms 6,940 KB
testcase_69	AC	3 ms 6,944 KB
testcase_70	AC	4 ms 6,940 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 {
public:
	using size_type = std::size_t;
	
private:
	size_type n;
	std::vector<int> dat;
	
public:
	UnionFind(size_type n) : n(n), dat(n, -1) {}
	
	size_type size(size_type x) {
		assert(x < n);
		return -dat[find(x)];
	}
	
	size_type find(size_type x) {
		assert(x < n);
		if (dat[x] < 0) return x;
		return dat[x] = find(dat[x]);
	}
	
	void unite(size_type x, size_type y) {
		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[x] += dat[y];
		dat[y] = x;
	}
	
	bool issame(size_type x, size_type y) {
		assert(x < n);
		assert(y < n);
		return find(x) == find(y);
	}
};

int main() {
	int N, M, S, T;
	cin >> N >> M >> S >> T; --S; --T;
	vector<int> P(N);
	REP(i, N) scanf("%d", &P[i]);
	vector<vector<int>> g(N);
	REP(i, M){
		int a, b;
		scanf("%d %d", &a, &b);
		--a; --b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	vector<int> ord(N);
	iota(ALL(ord), 0);
	sort(ALL(ord), [&](int i, int j) { return P[i] > P[j]; });
	int cur = P[S], ans = 0;
	UnionFind uf(N);
	for (int i : ord) {
		for (int v : g[i]) uf.unite(i, v);
		if (uf.issame(S, i) && chmin(cur, P[i])) ++ans;
	}
	cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード