結果
問題 | No.483 マッチ並べ |
ユーザー | arrows |
提出日時 | 2017-02-11 00:52:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,141 bytes |
コンパイル時間 | 1,123 ms |
コンパイル使用メモリ | 93,276 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-09 07:58:57 |
合計ジャッジ時間 | 2,621 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 2 ms
6,944 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,940 KB |
testcase_29 | AC | 1 ms
6,940 KB |
testcase_30 | AC | 2 ms
6,940 KB |
testcase_31 | AC | 2 ms
6,944 KB |
testcase_32 | AC | 2 ms
6,940 KB |
testcase_33 | AC | 2 ms
6,944 KB |
testcase_34 | AC | 2 ms
6,940 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,944 KB |
testcase_37 | AC | 2 ms
6,944 KB |
testcase_38 | AC | 2 ms
6,944 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 2 ms
6,940 KB |
testcase_41 | AC | 2 ms
6,940 KB |
testcase_42 | AC | 2 ms
6,944 KB |
testcase_43 | AC | 2 ms
6,940 KB |
testcase_44 | AC | 2 ms
6,940 KB |
testcase_45 | AC | 2 ms
6,940 KB |
testcase_46 | AC | 2 ms
6,944 KB |
testcase_47 | AC | 2 ms
6,940 KB |
testcase_48 | AC | 2 ms
6,944 KB |
testcase_49 | AC | 2 ms
6,940 KB |
testcase_50 | AC | 2 ms
6,944 KB |
testcase_51 | AC | 2 ms
6,944 KB |
testcase_52 | AC | 2 ms
6,944 KB |
testcase_53 | AC | 2 ms
6,944 KB |
testcase_54 | AC | 2 ms
6,944 KB |
testcase_55 | AC | 2 ms
6,944 KB |
ソースコード
#include <iostream> #include <vector> #include <map> #include <queue> #include <cstring> using namespace std; constexpr int MAX_V = 2525; constexpr int INF = (1 << 29); struct edge { int to, cap, rev; edge(int to, int cap, int rev) : to{to}, cap{cap}, rev{rev} {} }; vector<edge> G[MAX_V]; int level[MAX_V], iter[MAX_V]; void add_edge(int from, int to, int cap) { G[from].emplace_back(to, cap, G[to].size()); G[to].emplace_back(from, 0, G[from].size() - 1); } void bfs(int s) { memset(level, -1, sizeof(level)); queue<int> Q; level[s] = 0; Q.push(s); while (!Q.empty()) { int v = Q.front(); Q.pop(); for (int i = 0; i < (int)G[v].size(); i++) { edge& e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; Q.push(e.to); } } } } int dfs(int v, int t, int f) { if (v == t) return f; for (int& i = iter[v]; i < (int)G[v].size(); i++) { edge& e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; for (;;) { bfs(s); if (level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } } } int main() { int N, n = 0; cin >> N; map<pair<int, int>, int> mp; vector<int> a(N), b(N), c(N), d(N); for (int i = 0; i < N; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; if (mp.count(make_pair(a[i], b[i])) == 0) { mp[make_pair(a[i], b[i])] = n++; } if (mp.count(make_pair(c[i], d[i])) == 0) { mp[make_pair(c[i], d[i])] = n++; } } int S = n + N + 1, T = S + 1; for (int i = 0; i < N; i++) { add_edge(S, i, 1); add_edge(i, N + mp[make_pair(a[i], b[i])], 1); add_edge(i, N + mp[make_pair(c[i], d[i])], 1); } for (int i = 0; i < n; i++) { add_edge(i + N, T, 1); } cout << (max_flow(S, T) == N ? "YES" : "NO") << endl; return 0; }