AtCoder Beginner Contest 010

Submission #6908945

Source codeソースコード

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 3e5 + 10;
const int M = 5e5 + 10;

class Graph
{
public:
	int top[N];
	struct Node
	{
		int x, y, r, pre;
	} edge[M];
	int k;
	void init(int n = N)
	{
		k = 0;
		memset(top, -1, sizeof(int) * n);
	}
	inline void addEdge(int x, int y, int w)
	{
		edge[k] = Node{ x,y,w,top[x] };
		top[x] = k++;
		edge[k] = Node{ y,x,0,top[y] };
		top[y] = k++;
	}
	inline Node& operator[] (int i)
	{
		return edge[i];
	}

} g;
int s, t;
int current[N];
int layer[N];
bool bfs(int n)
{
	memset(layer, -1, sizeof(int) * n);
	queue<int> q;
	q.push(s);
	layer[s] = 1;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = g.top[x]; ~i; i = g[i].pre)
		{
			int y = g[i].y;
			int r = g[i].r;
			if (r > 0 && layer[y] == -1)
			{
				layer[y] = layer[x] + 1;
				if (y == t) return true;
				q.push(y);
			}
		}
	}
	return false;
}
int dfs(int x, int tot)
{
	if (x == t) return tot;
	int ret = 0;
	for (int i = current[x]; ~i; i = g[i].pre)
	{
		int y = g[i].y;
		int r = g[i].r;
		if (r > 0 && layer[y] == layer[x] + 1)
		{
			current[x] = i;
			int tmp = dfs(y, min(r, tot - ret));
			g[i].r -= tmp;
			g[i ^ 1].r += tmp;
			ret += tmp;
			if (ret == tot) return ret;
		}
	}
	layer[x] = -1;
	return ret;
}
int solve(int n)
{
	int ret = 0;
	while (bfs(n))
	{
		memcpy(current, g.top, sizeof(int) * n);
		ret += dfs(s, INF);
	}
	return ret;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, m, e;
	cin >> n >> m >> e;
	s = 1;
	t = 2 * n + 2;
	g.init(t + 1);
	for (int i = 0; i <= n; i++)
	{
		g.addEdge(i * 2, i * 2 + 1, INF);
	}
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		g.addEdge(x * 2 + 1, t, 1);
	}
	while (e--)
	{
		int x, y;
		cin >> x >> y;
		g.addEdge(x * 2 + 1, y * 2, 1);
		g.addEdge(y * 2 + 1, x * 2, 1);
	}
	cout << solve(t + 1) << endl;

	return 0;
}

Submission

Task問題 D - 浮気予防
User nameユーザ名 Heart_Blue
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2581 Byte
File nameファイル名
Exec time実行時間 4 ms
Memory usageメモリ使用量 2432 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 2 ms 2304 KB
sample_02.txt AC 2 ms 2304 KB
sample_03.txt AC 2 ms 2304 KB
sample_04.txt AC 2 ms 2304 KB
sample_05.txt AC 2 ms 2304 KB
test_01_AB.txt AC 2 ms 2304 KB
test_02_AB.txt AC 2 ms 2304 KB
test_03_AB.txt AC 2 ms 2304 KB
test_04_AB.txt AC 2 ms 2304 KB
test_05_AB.txt AC 2 ms 2304 KB
test_06_AB.txt AC 2 ms 2304 KB
test_07_AB.txt AC 2 ms 2304 KB
test_08_AB.txt AC 2 ms 2304 KB
test_09_AB.txt AC 2 ms 2304 KB
test_10_AB.txt AC 2 ms 2304 KB
test_11_AB.txt AC 2 ms 2304 KB
test_12_AB.txt AC 2 ms 2304 KB
test_13_AB.txt AC 2 ms 2304 KB
test_14_AB.txt AC 2 ms 2304 KB
test_15_AB.txt AC 2 ms 2304 KB
test_16_AB.txt AC 2 ms 2304 KB
test_17_AB.txt AC 2 ms 2304 KB
test_18_AB.txt AC 2 ms 2304 KB
test_19_AB.txt AC 2 ms 2304 KB
test_20_AB.txt AC 2 ms 2304 KB
test_21_AB.txt AC 2 ms 2304 KB
test_22_AB.txt AC 2 ms 2304 KB
test_23_AB.txt AC 2 ms 2304 KB
test_24_AB.txt AC 2 ms 2304 KB
test_25_AB.txt AC 2 ms 2304 KB
test_26_A.txt AC 4 ms 2304 KB
test_27_A.txt AC 4 ms 2304 KB
test_28_A.txt AC 4 ms 2432 KB
test_29_A.txt AC 4 ms 2304 KB
test_30_A.txt AC 4 ms 2304 KB
test_31_A.txt AC 4 ms 2304 KB
test_32_A.txt AC 2 ms 2304 KB
test_33_A.txt AC 3 ms 2304 KB
test_34_A.txt AC 2 ms 2304 KB
test_35_A.txt AC 2 ms 2304 KB
test_36_A.txt AC 2 ms 2304 KB
test_37_A.txt AC 2 ms 2304 KB
test_38_A.txt AC 2 ms 2304 KB
test_39_A.txt AC 2 ms 2304 KB
test_40_A.txt AC 2 ms 2304 KB
test_41_AB.txt AC 2 ms 2304 KB
test_42_A.txt AC 3 ms 2304 KB
test_43_A.txt AC 2 ms 2304 KB
test_44_A.txt AC 2 ms 2304 KB
test_45_A.txt AC 2 ms 2304 KB
test_46_A.txt AC 2 ms 2304 KB
test_47_AB.txt AC 2 ms 2304 KB
test_48_A.txt AC 2 ms 2304 KB
test_49_A.txt AC 2 ms 2304 KB
test_50_A.txt AC 2 ms 2304 KB
test_51_A.txt AC 2 ms 2304 KB