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

提出ソース

結果

問題	No.1382 Travel in Mitaru city
ユーザー	tkmst201
提出日時	2021-02-10 13:00:39
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	1,814 bytes
コンパイル時間	2,974 ms
コンパイル使用メモリ	210,040 KB
実行使用メモリ	11,408 KB
最終ジャッジ日時	2023-09-22 07:00:41
合計ジャッジ時間	9,381 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	WA	-
testcase_07	AC	22 ms 4,812 KB
testcase_08	WA	-
testcase_09	AC	30 ms 5,192 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	66 ms 10,540 KB
testcase_28	AC	63 ms 10,512 KB
testcase_29	AC	62 ms 10,644 KB
testcase_30	AC	65 ms 10,536 KB
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	43 ms 9,760 KB
testcase_37	AC	8 ms 4,376 KB
testcase_38	AC	47 ms 10,536 KB
testcase_39	AC	13 ms 4,964 KB
testcase_40	AC	36 ms 8,648 KB
testcase_41	AC	40 ms 9,160 KB
testcase_42	AC	47 ms 10,564 KB
testcase_43	AC	42 ms 9,444 KB
testcase_44	AC	18 ms 6,000 KB
testcase_45	AC	38 ms 8,916 KB
testcase_46	WA	-
testcase_47	WA	-
testcase_48	AC	37 ms 8,140 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	2 ms 4,380 KB
testcase_62	AC	2 ms 4,376 KB
testcase_63	AC	8 ms 4,376 KB
testcase_64	AC	3 ms 4,376 KB
testcase_65	AC	2 ms 4,380 KB
testcase_66	AC	3 ms 4,380 KB
testcase_67	AC	3 ms 4,376 KB
testcase_68	AC	4 ms 4,376 KB
testcase_69	AC	3 ms 4,376 KB
testcase_70	AC	5 ms 4,380 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;
//---------------------------------//

struct UnionFind {
public:
	using size_type = std::size_t;
	
	UnionFind(size_type n) : n(n), size_(n, 1) {
		par.resize(n);
		std::iota(par.begin(), par.end(), 0);
	}
	
	size_type size(size_type x) { return size_[find(x)]; }
	
	size_type find(size_type x) {
		assert(x < n);
		while (par[x] != x) {
			par[x] = par[par[x]];
			x = par[x];
		}
		return x;
	}
	
	void unite(size_type x, size_type y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (size(x) > size(y)) std::swap(x, y);
		par[x] = y;
		size_[y] += size_[x];
	}
	
	bool issame(size_type x, size_type y) { return find(x) == find(y); }
	
private:
	size_type n;
	std::vector<size_type> size_, par;
};

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

結果

テストケース

ソースコード