Submission #1206587

---

Source Code Expand

#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 Info

Judge Result