Submission #1206552

---

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, f, c, w;
};

int dd[MX];
int en[MX];
int go[MX];
vector<int> eds[MX];
vector<edge> ed;
int s, t;
int was[310][310];
char a[310][310];

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

int mincost() {
	int ans = 0;
	while (true) {
		for (int i = 0; i <= t; ++i)
			dd[i] = INF, en[i] = 0;
		queue<int> qu;
		qu.push(s);
		en[s] = 1;
		dd[s] = 0;
		go[s] = -1;
		while (!qu.empty()) {
			int x = qu.front();
			qu.pop();
			en[x] = 0;
			for (int e: eds[x]) {
				if (ed[e].f == ed[e].c)
					continue;
				int u = ed[e].b;
				if (dd[u] > dd[x] + ed[e].w) {
					dd[u] = dd[x] + ed[e].w;
					go[u] = e;
					if (!en[u])
						en[u] = 1, qu.push(u);
				}
			}
		}
		if (dd[t] == INF)
			break;
		++ans;
		int now = t;
		while (now != s) {
			int e = go[now];
			now = ed[e].a;
			ed[e].f += 1;
			ed[e ^ 1].f -= 1;
		}
	}
	return ans;
}

int n;

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

int U[310];
int D[310];
int L[310];
int R[310];

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 + n + n + n + 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, 0);
	for (int i = 0; i < n; ++i) {
		int x = n * n + i;
		add_edge(s, x, U[i], 0);
		for (int j = 0; j < n; ++j)
			add_edge(x, j * n + i, 1, j);
	}
	for (int i = 0; i < n; ++i) {
		int x = n * n + n + i;
		add_edge(s, x, D[i], 0);
		for (int j = 0; j < n; ++j)
			add_edge(x, j * n + i, 1, n - 1 - j);
	}
	for (int i = 0; i < n; ++i) {
		int x = n * n + n + n + i;
		add_edge(s, x, L[i], 0);
		for (int j = 0; j < n; ++j)
			add_edge(x, i * n + j, 1, j);
	}
	for (int i = 0; i < n; ++i) {
		int x = n * n + n + n + n + i;
		add_edge(s, x, R[i], 0);
		for (int j = 0; j < n; ++j)
			add_edge(x, i * n + j, 1, n - 1 - j);
	}
	int c = mincost();
	if (c < 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