AtCoder Beginner Contest 010

Submission #1574167

Source codeソースコード

#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;

const ll mod197 = 1000000007LL;
const ll INF = INT_MAX;

const double PI11 = 3.14159265359;

//最大公約数
ll gcd(ll a, ll b) {
	if ( a%b == 0 )
		return b;
	return gcd(b,a%b);
}

//最小公倍数
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

// (a ^ b) % mod
ll powMod(ll x, ll k, ll m) {
	if (k == 0)     return 1;
	if (k % 2 == 0) return powMod(x*x % m, k / 2, m);
	else            return x*powMod(x, k - 1, m) % m;
}

ll combi(ll n, ll k) {

	if (n < k) {
		swap(n, k);
	}

	ll a = 1, b = 1;

	for (ll i = n; i > n-k; i--) {
		a *= i;
		a %= mod197;
	}
	for (ll i = k; i > 0; i--) {
		b *= i;
		b %= mod197;
	}


	//cout << endl << a << " " << b << endl;

	//(n/a)%p = (n*a^(p-2))%p
	return (a*powMod(b, mod197 - 2, mod197)) % mod197;
}

//int main(void) {
//
//	ll a, b;
//	cin >> a >> b;
//
//	cout << combi(a+b-1, b) << endl;
//
//	return 0;
//}
//

struct edge {
	int to, cap, rev;

	edge() {
		to = cap = rev = -1;
	}
	edge(int t,int c,int r) : to(t), cap(c), rev(r) {

	}

};

using vedge = vector<edge>;

vedge arr[110] = {};

bool used[110] = {};

int n, g, e;

int dfs(int v, int t, int f) {
	if (v == t) return f;

	used[v] = true;

	for (int i = 0; i < arr[v].size(); i++) {
		edge &e = arr[v][i];

		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));

			//cout << v << " " << d << endl;

			if (d > 0) {
				e.cap -= d;
				arr[e.to][e.rev].cap += d;
				return d;
			}
		}
	}

	return 0;
}

int max_flow(int s,int t){

	int flow = 0;

	while (true) {

		fill(used,used+110,false);

		int f = dfs(s,t,INF);
		//cout << "flow " << f << endl;
		if (f == 0)return flow;
		flow += f;
	}

}

int main() {

	cin >> n >> g >> e;

	for (int i = 0; i < g; i++) {
		int p;
		cin >> p;

		arr[p].push_back(edge(n, 1, arr[n].size()));
		arr[n].push_back(edge(p, 1, arr[p].size() - 1));
	}

	for (int i = 0; i < e; i++) {
		int a, b;
		cin >> a >> b;

		arr[a].push_back(edge(b, 1, arr[b].size()));
		arr[b].push_back(edge(a, 1, arr[a].size()-1));

	}

	cout << max_flow(0,n) << endl;


	return 0;
}

Submission

Task問題 D - 浮気予防
User nameユーザ名 nasatame
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2608 Byte
File nameファイル名
Exec time実行時間 3 ms
Memory usageメモリ使用量 384 KB

Test case

Set

Set name Score得点 / Max score Cases
part 99 / 99 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 1 / 1 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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 AC 1 ms 256 KB
test_03_AB.txt AC 1 ms 256 KB
test_04_AB.txt AC 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 AC 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 AC 3 ms 384 KB
test_27_A.txt AC 3 ms 384 KB
test_28_A.txt AC 3 ms 384 KB
test_29_A.txt AC 3 ms 384 KB
test_30_A.txt AC 3 ms 384 KB
test_31_A.txt AC 3 ms 384 KB
test_32_A.txt AC 1 ms 256 KB
test_33_A.txt AC 2 ms 384 KB
test_34_A.txt AC 1 ms 256 KB
test_35_A.txt AC 2 ms 256 KB
test_36_A.txt AC 1 ms 256 KB
test_37_A.txt AC 2 ms 256 KB
test_38_A.txt AC 1 ms 256 KB
test_39_A.txt AC 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 AC 2 ms 256 KB
test_43_A.txt AC 1 ms 256 KB
test_44_A.txt AC 1 ms 256 KB
test_45_A.txt AC 1 ms 256 KB
test_46_A.txt AC 1 ms 256 KB
test_47_AB.txt AC 1 ms 256 KB
test_48_A.txt AC 1 ms 256 KB
test_49_A.txt AC 1 ms 256 KB
test_50_A.txt AC 1 ms 256 KB
test_51_A.txt AC 1 ms 256 KB