Submission #679488
Source Code Expand
#include <iostream> #include <vector> #include <cstring> #include <cmath> using namespace std; #define MAX_V 1010 int V; vector<int> G[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u); } bool dfs(int v) { used[v] = true; for (int i = 0; i < (int)G[v].size(); i++) { int u = G[v][i], w = match[u]; if (w < 0 || (!used[w] && dfs(w))) { match[v] = u; match[u] = v; return true; } } return false; } int bipartite_matching() { int res = 0; memset(match, -1, sizeof(match)); for (int v = 0; v < V; v++) { if (match[v] < 0) { memset(used, false, sizeof(used)); if (dfs(v)) { res++; } } } return res; } int main() { int T, n, m; cin >> T >> n; vector<int> A(n); for (int i = 0; i < n; i++) { cin >> A[i]; } cin >> m; vector<int> B(m); for (int i = 0; i < m; i++) { cin >> B[i]; for (int j = 0; j < n; j++) { if (B[i]-A[j] >= 0 && B[i]-A[j] <= T) { add_edge(i, m+j); } } } V = n + m; cout << (bipartite_matching() == m ? "yes" : "no") << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - おいしいたこ焼きの売り方 |
User | hot_cocoa |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 1309 Byte |
Status | AC |
Exec Time | 29 ms |
Memory | 936 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | rand0.txt, rand1.txt, rand10.txt, rand11.txt, rand12.txt, rand13.txt, rand14.txt, rand15.txt, rand16.txt, rand17.txt, rand18.txt, rand19.txt, rand2.txt, rand20.txt, rand21.txt, rand22.txt, rand23.txt, rand24.txt, rand25.txt, rand26.txt, rand27.txt, rand28.txt, rand29.txt, rand3.txt, rand4.txt, rand5.txt, rand6.txt, rand7.txt, rand8.txt, rand9.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
rand0.txt | AC | 24 ms | 924 KB |
rand1.txt | AC | 23 ms | 932 KB |
rand10.txt | AC | 23 ms | 804 KB |
rand11.txt | AC | 25 ms | 780 KB |
rand12.txt | AC | 25 ms | 924 KB |
rand13.txt | AC | 29 ms | 864 KB |
rand14.txt | AC | 25 ms | 804 KB |
rand15.txt | AC | 25 ms | 804 KB |
rand16.txt | AC | 25 ms | 808 KB |
rand17.txt | AC | 25 ms | 804 KB |
rand18.txt | AC | 25 ms | 740 KB |
rand19.txt | AC | 23 ms | 932 KB |
rand2.txt | AC | 25 ms | 932 KB |
rand20.txt | AC | 23 ms | 808 KB |
rand21.txt | AC | 25 ms | 804 KB |
rand22.txt | AC | 25 ms | 804 KB |
rand23.txt | AC | 25 ms | 804 KB |
rand24.txt | AC | 25 ms | 928 KB |
rand25.txt | AC | 25 ms | 924 KB |
rand26.txt | AC | 25 ms | 808 KB |
rand27.txt | AC | 25 ms | 804 KB |
rand28.txt | AC | 25 ms | 932 KB |
rand29.txt | AC | 24 ms | 932 KB |
rand3.txt | AC | 24 ms | 924 KB |
rand4.txt | AC | 25 ms | 808 KB |
rand5.txt | AC | 25 ms | 848 KB |
rand6.txt | AC | 25 ms | 808 KB |
rand7.txt | AC | 25 ms | 928 KB |
rand8.txt | AC | 25 ms | 928 KB |
rand9.txt | AC | 25 ms | 804 KB |
s1.txt | AC | 25 ms | 936 KB |
s2.txt | AC | 25 ms | 928 KB |
s3.txt | AC | 25 ms | 924 KB |
s4.txt | AC | 26 ms | 808 KB |
s5.txt | AC | 22 ms | 808 KB |