結果
問題 | No.1390 Get together |
ユーザー |
|
提出日時 | 2021-02-12 21:34:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 172 ms / 2,000 ms |
コード長 | 6,784 bytes |
コンパイル時間 | 2,292 ms |
コンパイル使用メモリ | 211,020 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2024-07-19 20:30:23 |
合計ジャッジ時間 | 6,189 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 5 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 5 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 4 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 119 ms
10,392 KB |
testcase_17 | AC | 161 ms
13,568 KB |
testcase_18 | AC | 132 ms
10,328 KB |
testcase_19 | AC | 172 ms
13,440 KB |
testcase_20 | AC | 167 ms
13,440 KB |
testcase_21 | AC | 166 ms
13,440 KB |
testcase_22 | AC | 146 ms
12,408 KB |
testcase_23 | AC | 152 ms
12,396 KB |
testcase_24 | AC | 151 ms
12,408 KB |
testcase_25 | AC | 166 ms
13,404 KB |
testcase_26 | AC | 170 ms
13,440 KB |
testcase_27 | AC | 170 ms
13,468 KB |
testcase_28 | AC | 168 ms
13,440 KB |
testcase_29 | AC | 169 ms
13,440 KB |
testcase_30 | AC | 165 ms
13,440 KB |
testcase_31 | AC | 170 ms
13,500 KB |
ソースコード
#pragma region library #ifdef __GNUC__ //#pragma GCC target("avx") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #endif #define _CRT_SECURE_NO_WARNINGS #include "bits/stdc++.h" // #include <boost/range/irange.hpp> // using boost::irange; #pragma region Macros #define itrall(x) std::begin(x), std::end(x) #define FOR(A,...) std::for_each(std::begin(A), std::end(A), [&]__VA_ARGS__ ) using i64 = long long; using cint = const int; using ci64 = const long long; using uint = unsigned int; using u64 = unsigned long long; using cuint = const unsigned int; using cu64 = const unsigned long long; #pragma endregion #ifndef CnM_library #define debug(x) constexpr int dx[] = { 1, 0, -1, 0 }; constexpr int dy[] = { 0, 1, 0, -1 }; template <class T> constexpr T INF_func() { return std::numeric_limits<T>::max(); } template <> constexpr int INF_func() { return 1001001001; } template <> constexpr long long INF_func() { return 1501501501501501501ll; } template <> constexpr unsigned int INF_func() { return 1001001001; } template <> constexpr unsigned long long INF_func() { return 1501501501501501501ll; } template <class T> constexpr T INF = INF_func<T>(); constexpr int mod = 1000000007; constexpr int mod2 = 998244353; #define elif else if #define len(T) (int)(T).size() template <class T, class U, class Comp = std::less<>> constexpr inline bool chmin(T& xmin, const U& x, Comp comp = {}) noexcept { return comp(x, xmin) ? xmin = x, true : false; } template <class T, class U, class Comp = std::less<>> constexpr inline bool chmax(T& xmax, const U& x, Comp comp = {}) noexcept { return comp(xmax, x) ? xmax = x, true : false; } namespace lib { template <class T, class U> inline T Pow(T A, U B) { T res(1); while (B) { if (B & 1) res *= A; A *= A; B >>= 1; } return res; } inline long long gcd(long long A, long long B) { while (B) { const long long C = A; A = B; B = C % B; } return A; } inline long long lcm(const long long A, const long long B) { return A / gcd(A, B) * B; } inline long long extgcd(long long A, long long B, long long& X, long long& Y) { long long D = A; if (B != 0) { D = extgcd(B, A % B, Y, X); Y -= (A / B) * X; return D; } else { X = 1; Y = 0; return A; } } inline long long modpow(long long A, long long B, const long long MOD) { long long res(1); while (B) { if (B & 1) res *= A, res %= MOD; A *= A; A %= MOD; B >>= 1; } return res; } template <class T> inline T inverse(T A, const T M) { T B = M, U = 1, V = 0; while (B) { T t = A / B; A -= t * B; std::swap(A, B); U -= t * V; std::swap(U, V); } U %= M; return U < 0 ? U += M, U : U; } } template <class T> inline void read(T& Tar) { std::cin >> Tar; return; } template <class T, class... Ts> inline void read(T& Tar, Ts&... ts) { std::cin >> Tar; read(ts...); return; } template <class T> inline void print(T Tar) { std::cout << Tar; return; } template <class T, class... Ts> inline void print(T Tar, Ts... ts) { std::cout << Tar; print(ts...); return; } #endif #pragma endregion class ProCon_all_init { static constexpr bool float_fixed = false; static constexpr int ios_perc = 15; static constexpr bool ios_fast = false; static constexpr bool flush_auto = false; public: ProCon_all_init() { if (ios_fast) { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); } if (float_fixed) { std::cout << std::fixed << std::setprecision(ios_perc); } if (flush_auto) { std::cout << std::unitbuf; } } } PROCON_ALL_INIT_; template <class T> std::vector<int> arg_sort(std::vector<T>& v, bool isgreater = false) { std::vector<int> res(v.size()); std::iota(res.begin(), res.end(), 0); std::sort(res.begin(), res.end(), [&](int i, int j) {return isgreater ? v[i] > v[j] : v[i] < v[j]; }); return res; } template <class T = long long> class range { const T First, Last; public: class iter { friend range; T itr; constexpr iter(T x) noexcept : itr(x) {} public: void operator ++() noexcept { itr++; } constexpr T operator *() const noexcept { return itr; } constexpr bool operator != (const iter x) const noexcept { return itr != x.itr; } }; constexpr range(const T F, const T L) noexcept : First(F), Last(std::max(F, L)) {} constexpr range(const T L) noexcept :First(0), Last(std::max((T)0, L)) {} constexpr iter begin() const noexcept { return iter(First); } constexpr iter end() const noexcept { return iter(Last); } /* * range(l, r) -> [l, r) * l < r */ }; template <class T = long long> class revge { const T First, Last; public: class reviter { friend revge; T itr; constexpr reviter(T x) noexcept : itr(x) {} public: void operator ++() noexcept { itr--; } constexpr T operator *() const noexcept { return itr; } constexpr bool operator != (const reviter x) const noexcept { return itr != x.itr; } }; constexpr revge(const T F, const T L) noexcept : First(std::max(L - 1, F)), Last(L) {} constexpr revge(const T F) noexcept : First(std::max((T)0, F)), Last(0) {} constexpr reviter begin() const noexcept { return reviter(First); } constexpr reviter end() const noexcept { return reviter(Last - 1); } /* * revge(r, l) -> [l, r] reverse * l >= r */ }; class dsu { int n; std::vector<int> par, rank; public: dsu() {} dsu(int n) : n(n), par(n, -1), rank(n, 0) {} void init(int N) { n = N; par.assign(N, -1); rank.assign(N, 0); } int root(int x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); }; bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (rank[x] < rank[y]) std::swap(x, y); if (rank[x] == rank[y]) rank[x]++; par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[root(x)]; }; }; class Get_together { public: int N, M; void solve() { read(N, M); std::vector<std::vector<int>> G(N); for (int i : range(N)) { int B, C; read(B, C); B--; C--; G[C].emplace_back(B); } dsu uft(M); for (int i : range(N)) { for (int j : range(len(G[i]) - 1)) { uft.merge(G[i][j], G[i][j + 1]); } } std::vector<bool> cnt(M, false); for (int i : range(M)) cnt[uft.root(i)] = true; i64 C = std::count(itrall(cnt), true); print(M - C, '\n'); } }; int main(void) { Get_together solver; solver.solve(); return 0; }