Submission #2215439
Source Code Expand
#include <bits/stdc++.h>
// #include "ane.cpp"
const int INF = 1e9;
const long long INFLL = 1e18;
const int NMAX = 105;
const int MMAX = 10005;
const int KMAX = 1005;
const int MOD = 1e9 + 7;
using namespace std;
// comment to disable debug functions
// #define DEBUG
// frequently used macros
#if __cplusplus >= 201103L
#define ALL(v) begin(v),end(v)
#define SORT(v) sort(begin(v), end(v))
#define FIND(v,x) find(begin(v), end(v), (x))
#else
#define ALL(v) (v).begin(),(v).end()
#define SORT(v) sort(v.begin(), v.end())
#define FIND(v,x) find(v.begin(), v.end(), (x))
#endif
#define fi first
#define se second
#define MEMNEXT(from, to) do{ memmove((to), (from), sizeof(from)); \
memset((from), 0, sizeof(from)); } while(0)
#ifdef DEBUG
#define DUMP(x) do{ std::cerr << (#x) << ": " << x << std::endl; }while(0)
#else
#define DUMP(x) do{}while(0)
#endif
// frequent used aliases
typedef long long ll;
typedef pair<int, int> p;
typedef pair<ll, int> lp;
typedef pair<ll, ll> llp;
typedef vector<int> vec;
typedef vector<ll> vecll;
typedef vector<vec> mat;
typedef vector<vecll> matll;
// frequently used constants
static const int di[] = {-1, 0, 1, -1, 1, -1, 0, 1};
static const int dj[] = {-1, -1, -1, 0, 0, 1, 1, 1};
// frequently used structs
struct edge{
int to,rev,cap;
};
// printf for debug
#ifndef DEBUG
void debug(const char* format, ...){}
#else
void debug(const char* format, ...){
va_list arg;
va_start(arg, format);
vprintf(format, arg);
va_end(arg);
}
#endif
// dump vector
#ifdef DEBUG
#define DUMPV(v, c) do{ \
printf("%s: ", #v); \
for (int i = 0; i < (c); ++i) \
{ \
cout << (v)[i] << " "; \
} \
cout << endl; \
} while(0)
#else
#define DUMPV(v,c)
#endif
// std::fill of multi dimensions
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
std::fill( (T*)array, (T*)(array+N), val );
}
// binary search
ll BSearch(ll _begin, ll _end, bool (*f)(ll)){
ll mid;
while(_end - _begin > 1LL) {
mid = _begin + (_end - _begin) / 2LL;
if(f(mid)) {
debug("BSearch: f(%d) == true\n", mid);
_end = mid;
}
else
{
debug("BSearch: f(%d) == false\n", mid);
_begin = mid;
}
}
return _end;
}
ll NUM_TEST_CASE = 1;
ll N,M,E;
bool used[NMAX];
vector<edge> G[NMAX];
ll ans = {};
void add_edge(int from, int to, int cap){
G[from].push_back(edge{to, (int)G[to].size(), cap});
G[to].push_back(edge{from, (int)G[from].size() - 1, 0});
}
int dfs(int i, int t, int f){
debug("dfs(%d, %d, %d)\n" ,i, t, f);
used[i] = true;
if (i == t || f == 0) return f;
for(auto&& e : G[i]) {
if(used[e.to]) continue;
if(ll ff = dfs(e.to, t, min(f, e.cap)) > 0)
{
e.cap -= ff;
G[e.to][e.rev].cap += ff;
return ff;
}
}
return 0;
}
ll max_flow(int s, int t){
ll ret = 0;
while(true) {
memset(used,false, NMAX);
int f = dfs(s, t, INF);
if(f == 0){
return ret;
}
ret += f;
}
}
void solve(){
// main algorithm
ans = max_flow(0, N);
}
void debug(){
// output debug information
for (int i = 0; i < N+1; ++i)
{
printf("G[%d]: ", i);
for(auto&& e : G[i]) {
printf("%d(<->G[%d][%d]):%d) ", e.to, i, e.rev, e.cap);
}
cout << endl;
}
}
void answer(){
// output answer
cout << ans << endl;
}
void init(){
// Fill(dp, -1);
}
int main(int argc, char const *argv[])
{
// operate inputs
// cin >> NUM_TEST_CASE;
for (int test_case = 0; test_case < NUM_TEST_CASE; ++test_case)
{
init();
cin >> N >> M >> E;
for (int i = 0; i < M; ++i)
{
int x;
scanf("%d", &x);
add_edge(x, N, 1);
}
for (int i = 0; i < E; ++i)
{
int a,b;
scanf("%d%d", &a, &b);
add_edge(a, b, 1);
add_edge(b, a, 1);
}
solve();
#ifdef DEBUG
debug();
#endif
answer();
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 浮気予防 |
User |
anekawa |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4128 Byte |
Status |
WA |
Exec Time |
3 ms |
Memory |
640 KB |
Compile Error
./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:182:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
./Main.cpp:188:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
Judge Result
Set Name |
part |
All |
Score / Max Score |
0 / 99 |
0 / 1 |
Status |
|
|
Set Name |
Test Cases |
part |
test_01_AB.txt, test_02_AB.txt, test_03_AB.txt, test_04_AB.txt, test_05_AB.txt, test_06_AB.txt, test_07_AB.txt, test_08_AB.txt, test_09_AB.txt, test_10_AB.txt, test_11_AB.txt, test_12_AB.txt, test_13_AB.txt, test_14_AB.txt, test_15_AB.txt, test_16_AB.txt, test_17_AB.txt, test_18_AB.txt, test_19_AB.txt, test_20_AB.txt, test_21_AB.txt, test_22_AB.txt, test_23_AB.txt, test_24_AB.txt, test_25_AB.txt, test_41_AB.txt, test_47_AB.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, test_01_AB.txt, test_02_AB.txt, test_03_AB.txt, test_04_AB.txt, test_05_AB.txt, test_06_AB.txt, test_07_AB.txt, test_08_AB.txt, test_09_AB.txt, test_10_AB.txt, test_11_AB.txt, test_12_AB.txt, test_13_AB.txt, test_14_AB.txt, test_15_AB.txt, test_16_AB.txt, test_17_AB.txt, test_18_AB.txt, test_19_AB.txt, test_20_AB.txt, test_21_AB.txt, test_22_AB.txt, test_23_AB.txt, test_24_AB.txt, test_25_AB.txt, test_26_A.txt, test_27_A.txt, test_28_A.txt, test_29_A.txt, test_30_A.txt, test_31_A.txt, test_32_A.txt, test_33_A.txt, test_34_A.txt, test_35_A.txt, test_36_A.txt, test_37_A.txt, test_38_A.txt, test_39_A.txt, test_40_A.txt, test_41_AB.txt, test_42_A.txt, test_43_A.txt, test_44_A.txt, test_45_A.txt, test_46_A.txt, test_47_AB.txt, test_48_A.txt, test_49_A.txt, test_50_A.txt, test_51_A.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
sample_04.txt |
AC |
1 ms |
256 KB |
sample_05.txt |
AC |
1 ms |
256 KB |
test_01_AB.txt |
AC |
1 ms |
256 KB |
test_02_AB.txt |
WA |
1 ms |
256 KB |
test_03_AB.txt |
WA |
1 ms |
256 KB |
test_04_AB.txt |
WA |
1 ms |
256 KB |
test_05_AB.txt |
AC |
1 ms |
256 KB |
test_06_AB.txt |
AC |
1 ms |
256 KB |
test_07_AB.txt |
AC |
1 ms |
256 KB |
test_08_AB.txt |
AC |
1 ms |
256 KB |
test_09_AB.txt |
AC |
1 ms |
256 KB |
test_10_AB.txt |
AC |
1 ms |
256 KB |
test_11_AB.txt |
WA |
1 ms |
256 KB |
test_12_AB.txt |
AC |
1 ms |
256 KB |
test_13_AB.txt |
AC |
1 ms |
256 KB |
test_14_AB.txt |
AC |
1 ms |
256 KB |
test_15_AB.txt |
AC |
1 ms |
256 KB |
test_16_AB.txt |
AC |
1 ms |
256 KB |
test_17_AB.txt |
AC |
1 ms |
256 KB |
test_18_AB.txt |
AC |
1 ms |
256 KB |
test_19_AB.txt |
AC |
1 ms |
256 KB |
test_20_AB.txt |
AC |
1 ms |
256 KB |
test_21_AB.txt |
AC |
1 ms |
256 KB |
test_22_AB.txt |
AC |
1 ms |
256 KB |
test_23_AB.txt |
AC |
1 ms |
256 KB |
test_24_AB.txt |
AC |
1 ms |
256 KB |
test_25_AB.txt |
AC |
1 ms |
256 KB |
test_26_A.txt |
WA |
2 ms |
512 KB |
test_27_A.txt |
WA |
2 ms |
640 KB |
test_28_A.txt |
WA |
2 ms |
640 KB |
test_29_A.txt |
WA |
2 ms |
640 KB |
test_30_A.txt |
WA |
3 ms |
640 KB |
test_31_A.txt |
WA |
2 ms |
512 KB |
test_32_A.txt |
WA |
1 ms |
256 KB |
test_33_A.txt |
WA |
2 ms |
384 KB |
test_34_A.txt |
WA |
1 ms |
256 KB |
test_35_A.txt |
WA |
1 ms |
256 KB |
test_36_A.txt |
WA |
1 ms |
256 KB |
test_37_A.txt |
WA |
1 ms |
384 KB |
test_38_A.txt |
WA |
1 ms |
256 KB |
test_39_A.txt |
WA |
1 ms |
256 KB |
test_40_A.txt |
AC |
1 ms |
256 KB |
test_41_AB.txt |
AC |
1 ms |
256 KB |
test_42_A.txt |
WA |
2 ms |
384 KB |
test_43_A.txt |
WA |
1 ms |
256 KB |
test_44_A.txt |
WA |
1 ms |
256 KB |
test_45_A.txt |
WA |
1 ms |
256 KB |
test_46_A.txt |
WA |
1 ms |
256 KB |
test_47_AB.txt |
WA |
1 ms |
256 KB |
test_48_A.txt |
WA |
1 ms |
256 KB |
test_49_A.txt |
WA |
1 ms |
256 KB |
test_50_A.txt |
WA |
1 ms |
256 KB |
test_51_A.txt |
WA |
1 ms |
256 KB |