CODE FESTIVAL 2016 Final

Submission #1206587

Source codeソースコード

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

#ifndef LOCAL
#define cerr _cer
struct _cert
{
    template <typename T> _cert& operator << (T) { return *this; }
};
_cert _cer;
#endif

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
		cerr << (*i) << " ";
    }
    cerr << "\n";
}
const int MX = 310 * 310 + 310 * 4;
const int INF = 1e9;


struct edge {
	int a, b, c, f;
};

vector<edge> ed;
vector<int> eds[MX];
int s, t;

int n;

int U[310];
int D[310];
int L[310];
int R[310];
char a[310][310];
int dd[MX];
int pp[MX];

void add_edge(int a, int b, int c) {
	edge x;
	x.a = a, x.b = b, x.c = c, x.f = 0;
	eds[a].push_back(ed.size());
	ed.push_back(x);
	swap(x.a, x.b);
	x.c = 0;
	eds[b].push_back(ed.size());
	ed.push_back(x);
}

int dfs1(int v, int fl) {
	if (v == t)
		return fl;
	if (dd[v] >= dd[t])
		return 0;
	int now = 0;
	for (; pp[v] < eds[v].size(); ++pp[v]) {
		int e = eds[v][pp[v]];
		int u = ed[e].b;
		if (ed[e].f == ed[e].c || dd[u] != dd[v] + 1)
			continue;
		int go = ed[e].c - ed[e].f;
		go = dfs1(u, min(fl, go));
		ed[e].f += go;
		ed[e ^ 1].f -= go;
		now += go;
		fl -= go;
		if (fl == 0)
			break;
	}
	return now;
}
queue<int> qu;

int dinic() {
	fill(dd, dd + t + 1, INF);
	qu.push(s);
	dd[s] = 0;
	while (!qu.empty()) {
		int x = qu.front();
		qu.pop();
		for (int e: eds[x]) {
			int u = ed[e].b;
			if (ed[e].f == ed[e].c)
				continue;
			if (dd[u] > dd[x] + 1)
				dd[u] = dd[x] + 1, qu.push(u);
		}
	}
	if (dd[t] == INF)
		return 0;
	fill(pp, pp + t + 1, 0);
	return dfs1(s, INF);
}

int flow() {
	int ans = 0;
	while (true) {
		int x = dinic();
		ans += x;
		if (!x)
			break;
	}
	return ans;
}

int us[310][310];
int was[310][310];

int dfs2(int x, int y) {
	if (us[x][y]) {
		us[x][y] = 0;
		return 1;
	}
	us[x][y] = 1;
	if (a[x][y] == 'L') {
		for (int i = 0; i < y; ++i) {
			if (!was[x][i] && dfs2(x, i)) {
				a[x][i] = 'L';
				if (us[x][y]) {
					us[x][y] = 0;
					return 1;
				}
				else {
					return dfs2(x, y);
				}
			}
		}
	}
	else if (a[x][y] == 'R') {
		for (int i = y + 1; i < n; ++i) {
			if (!was[x][i] && dfs2(x, i)) {
				a[x][i] = 'R';
				if (us[x][y]) {
					us[x][y] = 0;
					return 1;
				}
				else {
					return dfs2(x, y);
				}
			}
		}
	}
	else if (a[x][y] == 'U') {
		for (int i = 0; i < x; ++i) {
			if (!was[i][y] && dfs2(i, y)) {
				a[i][y] = 'U';
				if (us[x][y]) {
					us[x][y] = 0;
					return 1;
				}
				else {
					return dfs2(x, y);
				}
			}
		}
	}
	else {
		for (int i = x + 1; i < n; ++i) {
			if (!was[i][y] && dfs2(i, y)) {
				a[i][y] = 'D';
				if (us[x][y]) {
					us[x][y] = 0;
					return 1;
				}
				else {
					return dfs2(x, y);
				}
			}
		}
	}
	was[x][y] = 1;
	cout << a[x][y];
	if (a[x][y] == 'L' || a[x][y] == 'R')
		cout << x + 1 << "\n";
	else
		cout << y + 1 << "\n";
	return 0;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> U[i];
	for (int i = 0; i < n; ++i)
		cin >> D[i];
	for (int i = 0; i < n; ++i)
		cin >> L[i];
	for (int i = 0; i < n; ++i)
		cin >> R[i];
	s = n * n + 4 * n;
	t = s + 1;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			add_edge(i * n + j, t, 1);
	for (int i = 0; i < n; ++i) {
		int x = n * n + i;
		add_edge(s, x, U[i]);
		for (int j = 0; j < n; ++j)
			add_edge(x, j * n + i, 1);
	}
	for (int i = 0; i < n; ++i) {
		int x = n * n + n + i;
		add_edge(s, x, D[i]);
		for (int j = 0; j < n; ++j)
			add_edge(x, j * n + i, 1);
	}
	for (int i = 0; i < n; ++i) {
		int x = n * n + n + n + i;
		add_edge(s, x, L[i]);
		for (int j = 0; j < n; ++j)
			add_edge(x, i * n + j, 1);
	}
	for (int i = 0; i < n; ++i) {
		int x = n * n + n + n + n + i;
		add_edge(s, x, R[i]);
		for (int j = 0; j < n; ++j)
			add_edge(x, i * n + j, 1);
	}
	if (flow() < n * n) {
		cout << "NO\n";
		return 0;
	}
	for (edge e: ed) {
		if (e.f == 0 || e.a < n * n || e.b >= n * n)
			continue;
		int x = e.b / n;
		int y = e.b % n;
		int xx = e.a - n * n;
		if (xx < n)
			a[x][y] = 'U';
		else if (xx < 2 * n)
			a[x][y] = 'D';
		else if (xx < 3 * n)
			a[x][y] = 'L';
		else
			a[x][y] = 'R';
	}
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (!was[i][j]) {
				dfs2(i, j);
			}
	return 0;
}


Submission

Task問題 J - Neue Spiel
User nameユーザ名 LHiC
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 2100
Source lengthソースコード長 4764 Byte
File nameファイル名
Exec time実行時間 171 ms
Memory usageメモリ使用量 27876 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 2000 / 2000 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt
dataset2 100 / 100 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 2 ms 2560 KB
01-02.txt AC 2 ms 2560 KB
01-03.txt AC 2 ms 2560 KB
01-04.txt AC 2 ms 2560 KB
01-05.txt AC 3 ms 2688 KB
01-06.txt AC 3 ms 3016 KB
01-07.txt AC 4 ms 3144 KB
01-08.txt AC 4 ms 3144 KB
01-09.txt AC 3 ms 2688 KB
01-10.txt AC 4 ms 3144 KB
01-11.txt AC 4 ms 3144 KB
01-12.txt AC 4 ms 3144 KB
01-13.txt AC 4 ms 3144 KB
01-14.txt AC 2 ms 2560 KB
01-15.txt AC 4 ms 3140 KB
01-16.txt AC 4 ms 3144 KB
01-17.txt AC 4 ms 3144 KB
01-18.txt AC 4 ms 3144 KB
01-19.txt AC 3 ms 3016 KB
01-20.txt AC 4 ms 3144 KB
01-21.txt AC 4 ms 3144 KB
01-22.txt AC 4 ms 3016 KB
01-23.txt AC 4 ms 3016 KB
01-24.txt AC 4 ms 3144 KB
01-25.txt AC 4 ms 3144 KB
01-26.txt AC 3 ms 2816 KB
01-27.txt AC 3 ms 2816 KB
01-28.txt AC 4 ms 3144 KB
01-29.txt AC 4 ms 3144 KB
01-30.txt AC 4 ms 3144 KB
01-31.txt AC 4 ms 3016 KB
01-32.txt AC 4 ms 3144 KB
01-33.txt AC 4 ms 3016 KB
01-34.txt AC 4 ms 3144 KB
01-35.txt AC 3 ms 3144 KB
01-36.txt AC 3 ms 3144 KB
01-37.txt AC 3 ms 3016 KB
01-38.txt AC 4 ms 3144 KB
01-39.txt AC 4 ms 3144 KB
01-40.txt AC 4 ms 3144 KB
01-41.txt AC 4 ms 3144 KB
01-42.txt AC 4 ms 3144 KB
01-43.txt AC 3 ms 3144 KB
01-44.txt AC 4 ms 3144 KB
01-45.txt AC 4 ms 3144 KB
01-46.txt AC 4 ms 3144 KB
02-01.txt AC 106 ms 27492 KB
02-02.txt AC 117 ms 26596 KB
02-03.txt AC 91 ms 27492 KB
02-04.txt AC 106 ms 27876 KB
02-05.txt AC 88 ms 26340 KB
02-06.txt AC 90 ms 26340 KB
02-07.txt AC 87 ms 26340 KB
02-08.txt AC 94 ms 26980 KB
02-09.txt AC 77 ms 26596 KB
02-10.txt AC 171 ms 27236 KB
02-11.txt AC 77 ms 26212 KB
02-12.txt AC 160 ms 26596 KB
sample-01.txt AC 2 ms 2560 KB
sample-02.txt AC 2 ms 2560 KB