Submit Info #2647

Problem Lang User Status Time Memory
Matching on Bipartite Graph cpp14 jell AC 627 ms 34.88 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.66 MiB
random_00 AC 27 ms 14.98 MiB
random_01 AC 118 ms 29.68 MiB
random_02 AC 204 ms 25.98 MiB
random_03 AC 138 ms 24.14 MiB
random_04 AC 39 ms 17.43 MiB
random_05 AC 52 ms 15.31 MiB
random_06 AC 627 ms 34.88 MiB
random_07 AC 61 ms 18.01 MiB
random_08 AC 88 ms 30.88 MiB
random_09 AC 141 ms 29.61 MiB

#ifdef stderr_path #define LOCAL #endif #ifdef LOCAL #define _GLIBCXX_DEBUG #else #pragma GCC optimize("Ofast") #endif #include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <complex> #include <cstring> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> // #define NDEBUG #define debug_stream std::cerr #define iostream_untie true #define __precision__ 10 #define all(v) std::begin(v), std::end(v) #define rall(v) std::rbegin(v), std::rend(v) #define __odd(n) ((n) & 1) #define __even(n) (not __odd(n)) #define __popcount(n) __builtin_popcountll(n) #define __clz32(n) __builtin_clz(n) #define __clz64(n) __builtin_clzll(n) #define __ctz32(n) __builtin_ctz(n) #define __ctz64(n) __builtin_ctzll(n) using i32 = int_fast32_t; using i64 = int_fast64_t; using pii = std::pair<i32, i32>; using pll = std::pair<i64, i64>; template <class T> using heap = std::priority_queue<T>; template <class T> using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>; template <class T> constexpr T inf = std::numeric_limits<T>::max() / T(2) - T(1123456); namespace execution { std::chrono::system_clock::time_point start_time, end_time; void print_elapsed_time() { end_time = std::chrono::system_clock::now(); std::cerr << "\n----- Exec time : "; std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>( end_time - start_time) .count(); std::cerr << " ms -----\n\n"; } struct setupper { setupper() { if(iostream_untie) { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } std::cout << std::fixed << std::setprecision(__precision__); #ifdef stderr_path if(freopen(stderr_path, "a", stderr)) { std::cerr << std::fixed << std::setprecision(__precision__); } #endif #ifdef stdout_path if(not freopen(stdout_path, "w", stdout)) { freopen("CON", "w", stdout); std::cerr << "Failed to open the stdout file\n\n"; } std::cout << ""; #endif #ifdef stdin_path if(not freopen(stdin_path, "r", stdin)) { freopen("CON", "r", stdin); std::cerr << "Failed to open the stdin file\n\n"; } #endif #ifdef LOCAL std::cerr << "----- stderr at LOCAL -----\n\n"; atexit(print_elapsed_time); start_time = std::chrono::system_clock::now(); #else fclose(stderr); #endif } } __setupper; } // namespace execution class myclock_t { std::chrono::system_clock::time_point built_pt, last_pt; int built_ln, last_ln; std::string built_func, last_func; bool is_built; public: explicit myclock_t() : is_built(false) {} void build(int crt_ln, const std::string &crt_func) { is_built = true; last_pt = built_pt = std::chrono::system_clock::now(); last_ln = built_ln = crt_ln, last_func = built_func = crt_func; } void set(int crt_ln, const std::string &crt_func) { if(is_built) { last_pt = std::chrono::system_clock::now(); last_ln = crt_ln, last_func = crt_func; } else { debug_stream << "[ " << crt_ln << " : " << crt_func << " ] " << "myclock_t::set failed (yet to be built!)\n"; } } void get(int crt_ln, const std::string &crt_func) { if(is_built) { std::chrono::system_clock::time_point crt_pt( std::chrono::system_clock::now()); int64_t diff = std::chrono::duration_cast<std::chrono::milliseconds>(crt_pt - last_pt) .count(); debug_stream << diff << " ms elapsed from" << " [ " << last_ln << " : " << last_func << " ]"; if(last_ln == built_ln) debug_stream << " (when built)"; debug_stream << " to" << " [ " << crt_ln << " : " << crt_func << " ]" << "\n"; last_pt = built_pt, last_ln = built_ln, last_func = built_func; } else { debug_stream << "[ " << crt_ln << " : " << crt_func << " ] " << "myclock_t::get failed (yet to be built!)\n"; } } }; #ifdef LOCAL myclock_t __myclock; #define build_clock() __myclock.build(__LINE__, __func__) #define set_clock() __myclock.set(__LINE__, __func__) #define get_clock() __myclock.get(__LINE__, __func__) #else #define build_clock() ((void)0) #define set_clock() ((void)0) #define get_clock() ((void)0) #endif namespace std { template <class RAitr> void rsort(RAitr __first, RAitr __last) { sort(__first, __last, greater<>()); } template <class T> size_t hash_combine(size_t seed, T const &key) { return seed ^ (hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2)); } template <class T, class U> struct hash<pair<T, U>> { size_t operator()(pair<T, U> const &pr) const { return hash_combine(hash_combine(0, pr.first), pr.second); } }; template <class tuple_t, size_t index = tuple_size<tuple_t>::value - 1> struct tuple_hash_calc { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine( tuple_hash_calc<tuple_t, index - 1>::apply(seed, t), get<index>(t)); } }; template <class tuple_t> struct tuple_hash_calc<tuple_t, 0> { static size_t apply(size_t seed, tuple_t const &t) { return hash_combine(seed, get<0>(t)); } }; template <class... T> struct hash<tuple<T...>> { size_t operator()(tuple<T...> const &t) const { return tuple_hash_calc<tuple<T...>>::apply(0, t); } }; template <class T, class U> istream &operator>>(std::istream &s, pair<T, U> &p) { return s >> p.first >> p.second; } template <class T, class U> ostream &operator<<(std::ostream &s, const pair<T, U> p) { return s << p.first << " " << p.second; } template <class T> istream &operator>>(istream &s, vector<T> &v) { for(T &e : v) { s >> e; } return s; } template <class T> ostream &operator<<(ostream &s, const vector<T> &v) { bool is_front = true; for(const T &e : v) { if(not is_front) { s << ' '; } else { is_front = false; } s << e; } return s; } template <class tuple_t, size_t index> struct tupleos { static ostream &apply(ostream &s, const tuple_t &t) { tupleos<tuple_t, index - 1>::apply(s, t); return s << " " << get<index>(t); } }; template <class tuple_t> struct tupleos<tuple_t, 0> { static ostream &apply(ostream &s, const tuple_t &t) { return s << get<0>(t); } }; template <class... T> ostream &operator<<(ostream &s, const tuple<T...> &t) { return tupleos<tuple<T...>, tuple_size<tuple<T...>>::value - 1>::apply( s, t); } template <> ostream &operator<<(ostream &s, const tuple<> &t) { return s; } string revstr(string str) { reverse(str.begin(), str.end()); return str; } } // namespace std #ifdef LOCAL #define dump(...) \ debug_stream << "[ " << __LINE__ << " : " << __FUNCTION__ << " ]\n", \ dump_func(#__VA_ARGS__, __VA_ARGS__) template <class T> void dump_func(const char *ptr, const T &x) { debug_stream << '\t'; for(char c = *ptr; c != '\0'; c = *++ptr) { if(c != ' ') debug_stream << c; } debug_stream << " : " << x << '\n'; } template <class T, class... rest_t> void dump_func(const char *ptr, const T &x, rest_t... rest) { debug_stream << '\t'; for(char c = *ptr; c != ','; c = *++ptr) { if(c != ' ') debug_stream << c; } debug_stream << " : " << x << ",\n"; dump_func(++ptr, rest...); } #else #define dump(...) ((void)0) #endif template <class P> void read_range(P __first, P __second) { for(P i = __first; i != __second; ++i) std::cin >> *i; } template <class P> void write_range(P __first, P __second) { for(P i = __first; i != __second; std::cout << (++i == __second ? '\n' : ' ')) { std::cout << *i; } } // substitue y for x iff x > y. template <class T> bool chmin(T &x, const T &y) { return x > y ? x = y, true : false; } // substitue y for x iff x < y. template <class T> bool chmax(T &x, const T &y) { return x < y ? x = y, true : false; } // binary search. int_fast64_t bin(int_fast64_t ok, int_fast64_t ng, const std::function<bool(int_fast64_t)> &f) { while(std::abs(ok - ng) > 1) { int_fast64_t mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } // be careful that val is type-sensitive. template <class T, class A, size_t N> void init(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); } template <class A> void reset(A &array) { memset(array, 0, sizeof(array)); } /* The main code follows. */ main() { void __solve(); uint32_t t = 1; #ifdef LOCAL t = 1; #endif // cin >> t; while(t--) { __solve(); } } // Base class template <class cap_t, class cost_t> struct Flow { struct edge_t { size_t from, to; cap_t cap; cost_t cost; size_t rev; edge_t(size_t _from, size_t _to, cap_t _cap, cost_t _cost, size_t _rev) : from(_from), to(_to), cap(_cap), cost(_cost), rev(_rev) {} }; // struct edge_t protected: size_t V; std::vector<std::vector<edge_t>> adj; public: Flow(size_t _V) : V(_V), adj(_V) {} size_t size() const { return V; } std::vector<edge_t> &operator[](size_t v) { return adj[v]; } void add_edge(size_t from, size_t to, cap_t cap, cost_t cost) { adj[from].emplace_back(from, to, cap, cost, adj[to].size()); adj[to].emplace_back(to, from, 0, -cost, adj[from].size() - 1); } }; // struct Flow template <class cap_t> class Dinic : public Flow<cap_t, cap_t> { using Base = Flow<cap_t, cap_t>; std::vector<size_t> level, itr; bool bfs(size_t s, size_t t) { fill(level.begin(), level.end(), ~0); std::queue<size_t> que; que.emplace(s); level[s] = 0; while(!que.empty()) { size_t v = que.front(); que.pop(); for(const typename Base::edge_t &e : Base::adj[v]) { if(e.cap > cap_t(0) && not ~level[e.to]) { level[e.to] = level[v] + 1; que.emplace(e.to); } } } return ~level[t]; } cap_t dfs(size_t v, size_t t, cap_t f) { if(v == t) return f; cap_t res(0); while(itr[v] < Base::adj[v].size()) { typename Base::edge_t &e = Base::adj[v][itr[v]]; if(e.cap > cap_t(0) && level[v] < level[e.to]) { cap_t d = dfs(e.to, t, std::min(f, e.cap)); e.cap -= d; Base::adj[e.to][e.rev].cap += d; res += d; if((f -= d) == cap_t(0)) break; } ++itr[v]; } return res; } public: Dinic(size_t V) : Base::Flow(V), level(V), itr(V) {} void add_edge(size_t s, size_t t, cap_t cap) { Base::add_edge(s, t, cap, 0); } cap_t max_flow(size_t s, size_t t) { cap_t res = 0, f; while(bfs(s, t)) { fill(itr.begin(), itr.end(), 0); while((f = dfs(s, t, std::numeric_limits<cap_t>::max())) > cap_t(0)) res += f; } return res; } class cut_t { size_t V; bool* const data; friend class Dinic; public: cut_t(size_t _V) : V(_V), data(new bool[V]()) {} ~cut_t() { delete[] data; } size_t size() const { return V; } bool &operator[](size_t v) const { return data[v]; } bool *begin() const { return data; } bool *end() const { return data + V; } friend std::ostream &operator<<(std::ostream &s, const cut_t &cut) { bool is_front = true; for(bool b : cut) { if(is_front) is_front = false; else s << ' '; s << b; } return s; } }; // class cut_t cut_t min_cut(size_t s, size_t t) { while(bfs(s, t)) { fill(itr.begin(), itr.end(), 0); while(dfs(s, t, std::numeric_limits<cap_t>::max()) > cap_t(0)); } cut_t res(Base::V); for(size_t v = 0; v != Base::V; ++v) if(~level[v]) res.data[v] = 1; return res; } }; // class Dinic using namespace std; void __solve() { i32 l,r,m; cin>>l>>r>>m; Dinic<i32> dinic(l+r+2); const i32 s=l+r,t=s+1; for(i32 i = 0; i < m; ++i) { i32 a,b; cin>>a>>b; b+=l; dinic.add_edge(a,b,1); } for(i32 i = 0; i < l; ++i) { dinic.add_edge(s,i,1); } for(i32 i = 0; i < r; ++i) { dinic.add_edge(i+l,t,1); } cout << dinic.max_flow(s,t) << "\n"; for(i32 i = 0; i < l; ++i) { for(const auto &e : dinic[i]) { if(!e.cap and e.to<l+r) { cout << i << " " << e.to-l << "\n"; goto found; } } found: ; } }