結果
| 問題 | No.1639 最小通信路 |
| ユーザー |
 2 n
|
| 提出日時 | 2021-08-06 22:10:50 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,346 bytes |
| コンパイル時間 | 22,684 ms |
| コンパイル使用メモリ | 304,812 KB |
| 最終ジャッジ日時 | 2025-01-23 15:35:18 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 RE * 22 |
ソースコード
#pragma GCC target("avx2")//#pragma GCC target("avx")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#pragma GCC optimize("O3")//#pragma GCC optimize("Ofast")//#pragma GCC optimize("unroll-loops")// #include<bits/stdc++.h>#include <boost/range/irange.hpp>#include <boost/range/join.hpp>#include <boost/range/algorithm.hpp>// #include <boost/range/adaptor/copied.hpp>#include <boost/range/adaptor/filtered.hpp>#include <boost/range/adaptor/indexed.hpp>#include <boost/range/adaptor/indirected.hpp>#include <boost/range/adaptor/map.hpp>#include <boost/range/adaptor/ref_unwrapped.hpp>// #include <boost/range/adaptor/replaced.hpp>// #include <boost/range/adaptor/replaced_if.hpp>#include <boost/range/adaptor/reversed.hpp>// #include <boost/range/adaptor/sliced.hpp>// #include <boost/range/adaptor/strided.hpp>// #include <boost/range/adaptor/type_erased.hpp>// #include <boost/range/adaptor/tokenized.hpp>#include <boost/range/adaptor/transformed.hpp>#include <boost/range/adaptor/uniqued.hpp>using namespace boost::adaptors;// #include <array>#include <vector>// #include <list>// #include <forward_list>#include <deque>#include <queue>#include <stack>// #include <bitset>#include <unordered_map>#include <map>#include <unordered_set>#include <set>#include <algorithm>#include <string>#include <iostream>#include <iomanip>// #include <sstream>// #include <bit>// #include <complex>// #include <exception>// #include <fstream>// #include <functional>// #include <iosfwd>// #include <iterator>// #include <limits>// #include <locale>// #include <memory>// #include <new>// #include <numeric>// #include <stdexcept>// #include <typeinfo>// #include <utility>// #include <valarray>// #include <atomic>// #include <chrono>// #include <condition_variable>// #include <future>// #include <mutex>// #include <random>// #include <ratio>// #include <regex>// #include <scoped_allocator>// #include <system_error>// #include <thread>// #include <tuple>// #include <typeindex>// #include <type_traits>// #include <cctype>// #include <cerrno>// #include <cfloat>// #include <ciso646>// #include <climits>// #include <clocale>#include <cmath>// #include <csetjmp>// #include <csignal>// #include <cstdarg>// #include <cstddef>// #include <cstdio>// #include <cstdlib>// #include <cstring>#include <ctime>// #include <ccomplex>// #include <cfenv>// #include <cinttypes>// #include <cstdbool>// #include <cstdint>// #include <ctgmath>// #include <cwchar>// #include <cwctype>using namespace std;#include <atcoder/all>using namespace atcoder;#define STRINGIFY(n) #n#define TOSTRING(n) STRINGIFY(n)using ll = long long;using ull = unsigned long long;template<typename T> using maxque = priority_queue<T>;template<typename T> using minque = priority_queue<T,vector<T>,greater<T>>;#define int ll#define endl "\n"#define unless(cond) if(!(cond))#define until(cond) while(!(cond))#define rep(i,s,e) for(ll i = (s); i < (e); ++i)#define repR(i,s,e) for(ll i = (e)-1; (s) <= i; --i)#define repE(i,s,e) for(ll i = (s); i <= (e); ++i)#define repER(i,s,e) for(ll i = (e); (s) <= i; --i)#define repSubsetR(set,super) for(ll _super=super,set = _super; 0 <= set; --set)if(set &= _super, true)#define ALL(xs) begin(xs), end(xs)#define ALLR(xs) rbegin(xs), rend(xs)#define ALLC(xs) cbegin(xs), cend(xs)#define ALLCR(xs) crbegin(xs), crend(xs)template<typename C> void uniq(C &xs){ xs.erase(unique(ALL(xs)), xs.end()); }template<typename C> constexpr ll len(C &&xs){ return size(forward<C>(xs)); }ll BIT(ll n){ return 1LL<<n; }auto clock0 = clock();void debug_h(const char *file, signed line, const char *str_args){ cerr << file << ":" << line << ": " << str_args << " => "; }template<class X, class... Xs> void debug_(const X &x, const Xs&... xs){ cerr << x; (void)initializer_list<int>{ (cerr << ", " << xs,0)... };cerr <<endl; }void debug_(){ cerr << endl; }#define ASSERT(pred,...) (static_cast<bool>(pred) ? void(0) : (debug_h(__FILE__, __LINE__, "ASSERT FAIL! " #pred "; " #__VA_ARGS__),debug_(__VA_ARGS__),exit(1)))template<class X> X &&dbg_(X &&x){ cerr<<x<<endl; return forward<X>(x); }#ifdef DEBUG#define dbg(x) (debug_h(__FILE__, __LINE__, "" #x),dbg_(x))#define debug(...) (debug_h(__FILE__, __LINE__, "" #__VA_ARGS__),debug_(__VA_ARGS__))#define clk(...) (cerr << __VA_ARGS__ " @ " << (clock()-clock0) <<endl,(void)0)#else#define dbg(x) (x)#define debug(...) ((void)0)#define clk(...) ((void)0)//#define ASSERT(pred,...) ((void)0)#endif#define DEF_ORD(op) bool operator op(SELF_ const &b)const { return Ord() op b.Ord(); }#define ORD(...) auto Ord()const{ return tie(__VA_ARGS__); } typedef auto self_fn_() -> decltype(*this); using SELF_ = decltype(((self_fn_*)nullptr)()); DEF_ORD(==) DEF_ORD(!=) DEF_ORD(<) DEF_ORD(>) DEF_ORD(<=) DEF_ORD(>=)template<class C> auto operator<<(ostream &out, const C &xs) -> enable_if_t<!is_same_v<decay_t<C>, char*> && !is_same_v<decay_t<C>, string>, decltype(begin(xs),out)&> { out<<"[ "; for(auto&&x:xs)out<<x<<", "; return out<<"]"; }template<class C> auto operator>>(istream &in, C &xs) -> enable_if_t<!is_same_v<decay_t<C>, char*> && !is_same_v<decay_t<C>, string>, decltype(begin(xs),in)&> { for(auto&x:xs)in>>x; return in; }template<class Tuple, size_t... I> void print_tuple_(ostream &out, Tuple const &xs, std::index_sequence<I...>){ out << "("; (void)initializer_list<int>{ (out << (I==0?"":", ") << std::get<I>(xs),0)... }; out << ")"; }template<class... T> ostream &operator<<(ostream &out, tuple<T...> const &xs){ print_tuple_(out, xs, make_index_sequence<sizeof...(T)>()); return out; }template<class Tuple, size_t... I> void read_tuple_(istream &in, Tuple &xs, std::index_sequence<I...>){ (void)initializer_list<int>{ (in >> std::get<I>(xs),0)... }; }template<class... T> istream &operator>>(istream &in, tuple<T...> &xs){ read_tuple_(in, xs, make_index_sequence<sizeof...(T)>()); return in; }template<class S, class T> ostream &operator<<(ostream &out, pair<S, T> const &p){ return out << "(" << p.first << ", " << p.second << ")"; }template<class S, class T> istream &operator>>(istream &in, pair<S, T> &p){ return in >> p.first >> p.second; }template<typename MINT, typename = internal::is_modint_t<MINT>> ostream &operator<<(ostream &out, MINT x){ return out << x.val(); }template<typename MINT, typename = internal::is_modint_t<MINT>> istream &operator>>(istream &in, MINT &x){ ll a; in>>a; x = a; return in; }template<typename... X> void _cin(X &... x){ (cin >> ... >> x); }#define CIN(...) __VA_ARGS__; _cin(__VA_ARGS__)template<typename F> struct Fix : F {template<typename G> Fix(G &&g) : F{forward<G>(g)} {}template<typename... Xs> decltype(auto) operator()(Xs&&... xs)const{ return F::operator()(*this, forward<Xs>(xs)...); }};template<typename F> Fix(F&&) -> Fix<decay_t<F>>;template<typename T,typename U> bool chmin(T &a, U b){ if(a <= b)return false; a = b; return true; }template<typename T,typename U> bool chmax(T &a, U b){ if(a >= b)return false; a = b; return true; }//const signed MOD = 998244353;const signed MOD = 1000000007; // 10^9+7using mint = static_modint<MOD>;// using mint = dynamic_modint<-1>; // mint::set_mod(mod);// using mint0 = dynamic_modint<0>; // mint0::set_mod(mod);const ll INF = BIT(60);ll solve(){ll CIN(n);vector<tuple<ll,ll,ll>> edges(n*(n-1)/2);rep(i,0,len(edges)){ll CIN(a,b,c);--a;--b;debug(a,b,c);edges[i] = {c,a,b};}sort(ALL(edges));ll union_cnt = n;vector<ll> par(n); iota(ALL(par),0);Fix root = [&](auto root, ll v)->ll{ll p = par[v];if(p == v) return p;return par[v] = root(p);};for(auto [c,a,b] : edges){auto ra = root(a);auto rb = root(b);if(ra == rb) continue;par[rb] = ra;if(--union_cnt==1) return c;}exit(1);}signed main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(15);try{cout << solve() << endl;/*cout << (solve()?"Yes":"No") << endl; // */return 0;}catch(exception& e){cerr << e.what() << endl;}catch(char *s){cerr << s << endl;}return 1;}