結果
問題 | No.1390 Get together |
ユーザー | komori3 |
提出日時 | 2021-02-12 22:15:28 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 7,592 bytes |
コンパイル時間 | 2,300 ms |
コンパイル使用メモリ | 212,928 KB |
実行使用メモリ | 25,024 KB |
最終ジャッジ日時 | 2023-09-27 04:33:31 |
合計ジャッジ時間 | 6,132 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,376 KB |
testcase_04 | AC | 3 ms
4,376 KB |
testcase_05 | AC | 3 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,376 KB |
testcase_07 | AC | 3 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 3 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 117 ms
21,328 KB |
testcase_17 | AC | 76 ms
20,716 KB |
testcase_18 | AC | 162 ms
25,024 KB |
testcase_19 | AC | 115 ms
24,180 KB |
testcase_20 | AC | 117 ms
24,292 KB |
testcase_21 | AC | 117 ms
24,092 KB |
testcase_22 | AC | 138 ms
24,676 KB |
testcase_23 | AC | 142 ms
24,476 KB |
testcase_24 | AC | 139 ms
24,440 KB |
testcase_25 | AC | 121 ms
24,220 KB |
testcase_26 | AC | 124 ms
24,100 KB |
testcase_27 | AC | 115 ms
24,172 KB |
testcase_28 | AC | 122 ms
24,144 KB |
testcase_29 | AC | 121 ms
24,116 KB |
testcase_30 | AC | 123 ms
24,288 KB |
testcase_31 | AC | 131 ms
24,220 KB |
ソースコード
// #define _NDEBUG #define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include "bits/stdc++.h" #include <unordered_map> #include <unordered_set> #ifdef _MSC_VER #include <ppl.h> #include <concurrent_vector.h> #include <filesystem> //#include <boost/multiprecision/cpp_dec_float.hpp> //#include <boost/multiprecision/cpp_int.hpp> //#include <boost/rational.hpp> #include <opencv2/core.hpp> #include <opencv2/imgproc.hpp> #include <opencv2/highgui.hpp> //#else //#include <omp.h> #endif /* type */ using uint = unsigned; using ll = long long; using ull = unsigned long long; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; /* io */ template <typename _KTy, typename _Ty> std::ostream& operator << (std::ostream& o, const std::pair<_KTy, _Ty>& m) { o << "[" << m.first << ", " << m.second << "]"; return o; } template <typename _KTy, typename _Ty> std::ostream& operator << (std::ostream& o, const std::map<_KTy, _Ty>& m) { if (m.empty()) { o << "[]"; return o; } o << "[" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "]"; return o; } template <typename _KTy, typename _Ty> std::ostream& operator << (std::ostream& o, const std::unordered_map<_KTy, _Ty>& m) { if (m.empty()) { o << "[]"; return o; } o << "[" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "]"; return o; } template <typename _Ty> std::ostream& operator << (std::ostream& o, const std::vector<_Ty>& v) { if (v.empty()) { o << "[]"; return o; } o << "[" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "]"; return o; } template <typename _Ty> std::ostream& operator << (std::ostream& o, const std::deque<_Ty>& v) { if (v.empty()) { o << "[]"; return o; } o << "[" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "]"; return o; } template <typename _Ty> std::ostream& operator << (std::ostream& o, const std::set<_Ty>& s) { if (s.empty()) { o << "[]"; return o; } o << "[" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "]"; return o; } template <typename _Ty> std::ostream& operator << (std::ostream& o, const std::unordered_set<_Ty>& s) { if (s.empty()) { o << "[]"; return o; } o << "[" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "]"; return o; } template <typename _Ty> std::ostream& operator << (std::ostream& o, const std::stack<_Ty>& s) { if (s.empty()) { o << "[]"; return o; } std::stack<_Ty> t(s); o << "[" << t.top(); t.pop(); while (!t.empty()) { o << ", " << t.top(); t.pop(); } o << "]"; return o; } template <typename _Ty> std::ostream& operator << (std::ostream& o, const std::list<_Ty>& l) { if (l.empty()) { o << "[]"; return o; } o << "[" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "]"; return o; } template <typename _KTy, typename _Ty> std::istream& operator >> (std::istream& is, std::pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; } template <typename _Ty> std::istream& operator >> (std::istream& is, std::vector<_Ty>& v) { for (size_t t = 0; t < v.size(); t++) is >> v[t]; return is; } template <typename _Ty> std::istream& operator >> (std::istream& is, std::deque<_Ty>& v) { for (size_t t = 0; t < v.size(); t++) is >> v[t]; return is; } namespace aux { // print tuple template<typename Ty, unsigned N, unsigned L> struct tp { static void print(std::ostream& os, const Ty& v) { os << std::get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } }; template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(std::ostream& os, const Ty& v) { os << std::get<N>(v); } }; } template<typename... Tys> std::ostream& operator<<(std::ostream& os, const std::tuple<Tys...>& t) { os << "["; aux::tp<std::tuple<Tys...>, 0, sizeof...(Tys) - 1>::print(os, t); os << "]"; return os; } /* fill */ template<typename A, size_t N, typename T> void Fill(A(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); } /* format */ template <typename ... Args> std::string format(const std::string& fmt, Args ... args) { size_t len = std::snprintf(nullptr, 0, fmt.c_str(), args ...); std::vector<char> buf(len + 1); std::snprintf(&buf[0], len + 1, fmt.c_str(), args ...); return std::string(&buf[0], &buf[0] + len); } /* dump */ #define DUMPOUT std::cerr #define dump(...) do{DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :[DUMP - "<<__LINE__<<":"<<__FUNCTION__<<"]"<<std::endl;DUMPOUT<<" ";dump_func(__VA_ARGS__);}while(0); void dump_func() { DUMPOUT << std::endl; } template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); } /* timer */ class Timer { public: double t = 0; Timer() { reset(); } static double time() { #ifdef _MSC_VER return __rdtsc() / 2.8e9; #else unsigned long long a, d; __asm__ volatile("rdtsc" : "=a"(a), "=d"(d)); return (d << 32 | a) / 2.8e9; #endif } //void measure() { t = time() - t; } void reset() { t = time(); } double elapsedMs() { return (time() - t) * 1000.0; } } timer; /* rand */ struct Xorshift { uint64_t x = 88172645463325252LL; unsigned next_int() { x = x ^ (x << 7); return x = x ^ (x >> 9); } unsigned next_int(unsigned mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return x % mod; } unsigned next_int(unsigned l, unsigned r) { x = x ^ (x << 7); x = x ^ (x >> 9); return x % (r - l + 1) + l; } double next_double() { return double(next_int()) / UINT_MAX; } } rnd; /* shuffle */ template<typename T> void shuffle_vector(std::vector<T>& v, Xorshift& rnd) { int n = v.size(); for (int i = n - 1; i >= 1; i--) { int r = rnd.next_int(i); std::swap(v[i], v[r]); } } using namespace std; class DisjointSet { private: vector<int> par; vector<int> rank; vector<int> sz; // 要素の個数 int set_sz; // 集合の個数 public: DisjointSet() : set_sz(0) {} DisjointSet(int n) { init(n); } void init(int n) { par.resize(n); rank.resize(n, 0); sz.resize(n, 1); set_sz = n; for (int i = 0; i < n; i++) par[i] = i; } int set_size() { return set_sz; } int size(int v) { return sz[root(v)]; } int root(int x) { if (par[x] == x) return x; else return par[x] = root(par[x]); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) return; if (rank[x] < rank[y]) par[x] = y; else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; } sz[x] += sz[y]; sz[y] = sz[x]; set_sz--; } bool same(int x, int y) { return root(x) == root(y); } friend ostream& operator<<(ostream& o, const DisjointSet& ds) { o << "\nparent : " << ds.par << "\nrank : " << ds.rank << "\nsize : " << ds.sz << "\nsize of set : " << ds.set_sz << '\n'; return o; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; DisjointSet ds(M); // どの箱をマージするか vector<set<int>> pos(N); // 色 c が存在する場所 for (int i = 0; i < N; i++) { int b, c; cin >> b >> c; b--; c--; pos[c].insert(b); } for (const auto& st : pos) { if (st.size() <= 1) continue; vector<int> v(st.begin(), st.end()); int sz = v.size(), u = v[0]; for (int i = 1; i < sz; i++) { ds.unite(u, v[i]); } } cout << M - ds.set_size() << endl; return 0; }