Submit Info #2679

Problem Lang User Status Time Memory
Matching on Bipartite Graph cpp (anonymous) WA 61 ms 8.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.67 MiB
line_00 AC 29 ms 8.34 MiB
line_01 AC 30 ms 8.28 MiB
many_smalls_00 AC 30 ms 5.25 MiB
many_smalls_01 AC 32 ms 5.29 MiB
max_random_00 WA 44 ms 7.75 MiB
max_random_01 AC 43 ms 7.76 MiB
max_random_02 AC 46 ms 7.80 MiB
random_00 AC 8 ms 1.83 MiB
random_01 AC 28 ms 5.17 MiB
random_02 AC 19 ms 4.39 MiB
random_03 AC 61 ms 3.77 MiB
random_04 AC 8 ms 2.00 MiB
random_05 AC 14 ms 3.52 MiB
random_06 AC 47 ms 5.34 MiB
random_07 AC 13 ms 4.52 MiB
random_08 AC 12 ms 2.18 MiB
random_09 AC 28 ms 5.02 MiB

#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (int)(n); i++) //fast IO by yosupo template<class t> using V=vector<t>; template<class t> using VV=V<V<t>>; struct Scanner { FILE* fp = nullptr; char line[(1 << 15) + 1]; size_t st = 0, ed = 0; void reread() { memmove(line, line + st, ed - st); ed -= st; st = 0; ed += fread(line + ed, 1, (1 << 15) - ed, fp); line[ed] = '\0'; } bool succ() { while (true) { if (st == ed) { reread(); if (st == ed) return false; } while (st != ed && isspace(line[st])) st++; if (st != ed) break; } if (ed - st <= 50) reread(); return true; } template <class T, enable_if_t<is_same<T, string>::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; while (true) { size_t sz = 0; while (st + sz < ed && !isspace(line[st + sz])) sz++; ref.append(line + st, sz); st += sz; if (!sz || st != ed) break; reread(); } return true; } template <class T, enable_if_t<is_integral<T>::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } ref = T(0); while (isdigit(line[st])) { ref = 10 * ref + (line[st++] - '0'); } if (neg) ref = -ref; return true; } template <class T> bool read_single(V<T>& ref) { for (auto& d : ref) { if (!read_single(d)) return false; } return true; } void read() {} template <class H, class... T> void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } Scanner(FILE* _fp) : fp(_fp) {} }; struct Printer { public: template <bool F = false> void write() {} template <bool F = false, class H, class... T> void write(const H& h, const T&... t) { if (F) write_single(' '); write_single(h); write<true>(t...); } template <class... T> void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fp(_fp) {} ~Printer() { flush(); } private: static constexpr size_t SIZE = 1 << 15; FILE* fp; char line[SIZE], small[50]; size_t pos = 0; void flush() { fwrite(line, 1, pos, fp); pos = 0; } void write_single(const char& val) { if (pos == SIZE) flush(); line[pos++] = val; } template <class T, enable_if_t<is_integral<T>::value, int> = 0> void write_single(T val) { if (pos > (1 << 15) - 50) flush(); if (val == 0) { write_single('0'); return; } if (val < 0) { write_single('-'); val = -val; // todo min } size_t len = 0; while (val) { small[len++] = char('0' + (val % 10)); val /= 10; } reverse(small, small + len); memcpy(line + pos, small, len); pos += len; } void write_single(const string& s) { for (char c : s) write_single(c); } void write_single(const char* s) { size_t len = strlen(s); for (size_t i = 0; i < len; i++) write_single(s[i]); } template <class T> void write_single(const V<T>& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; struct BiMatching { int val = 0; vector<int> used,p,q; vector<vector<int> > g; BiMatching(int L, int R) : used(L,0), p(L,-1), q(R,-1), g(L) {} void add_edge(int x, int y) { g[x].push_back(y); } bool dfs(int x) { if (used[x] == val) return false; used[x] = val; for (int y : g[x]) { if (q[y] >= 0 && !dfs(q[y])) continue; p[x] = y, q[y] = x; return true; } return false; } int run() { int match = 0, u = 1; while (u) { u = 0, val = ~val; rep (i,p.size()) if (!~p[i] && dfs(i)) u = 1, ++match; } return match; } }; int32_t main() { Scanner sc(stdin); Printer pr(stdout); int L,R,M; sc.read(L,R,M); BiMatching bm(L,R); rep (i,M) { int a,b; sc.read(a,b); bm.add_edge(a,b); } pr.writeln(bm.run()); rep (i,L) if (bm.p[i] >= 0) pr.writeln(i, bm.p[i]); }