CODE FESTIVAL 2016 Final

Submission #1206552

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, 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

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

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 0 / 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 3 ms 2560 KB
01-05.txt AC 8 ms 2688 KB
01-06.txt AC 34 ms 3072 KB
01-07.txt AC 129 ms 3164 KB
01-08.txt AC 121 ms 3164 KB
01-09.txt AC 6 ms 2688 KB
01-10.txt AC 112 ms 3072 KB
01-11.txt AC 128 ms 3164 KB
01-12.txt AC 130 ms 3164 KB
01-13.txt AC 127 ms 3164 KB
01-14.txt AC 2 ms 2560 KB
01-15.txt AC 93 ms 3072 KB
01-16.txt AC 128 ms 3164 KB
01-17.txt AC 131 ms 3164 KB
01-18.txt AC 130 ms 3164 KB
01-19.txt AC 127 ms 3072 KB
01-20.txt AC 140 ms 3164 KB
01-21.txt AC 143 ms 3164 KB
01-22.txt AC 143 ms 3072 KB
01-23.txt AC 165 ms 3072 KB
01-24.txt AC 164 ms 3164 KB
01-25.txt AC 167 ms 3164 KB
01-26.txt AC 27 ms 2816 KB
01-27.txt AC 29 ms 2944 KB
01-28.txt AC 144 ms 3072 KB
01-29.txt AC 167 ms 3164 KB
01-30.txt AC 160 ms 3164 KB
01-31.txt AC 159 ms 3072 KB
01-32.txt AC 164 ms 3164 KB
01-33.txt AC 162 ms 3072 KB
01-34.txt AC 163 ms 3164 KB
01-35.txt AC 52 ms 3072 KB
01-36.txt AC 58 ms 3164 KB
01-37.txt AC 47 ms 3072 KB
01-38.txt AC 103 ms 3072 KB
01-39.txt AC 110 ms 3164 KB
01-40.txt AC 94 ms 3072 KB
01-41.txt AC 104 ms 3164 KB
01-42.txt AC 103 ms 3164 KB
01-43.txt AC 81 ms 3164 KB
01-44.txt AC 92 ms 3164 KB
01-45.txt AC 81 ms 3164 KB
01-46.txt AC 92 ms 3164 KB
02-01.txt TLE
02-02.txt TLE
02-03.txt TLE
02-04.txt TLE
02-05.txt TLE
02-06.txt TLE
02-07.txt TLE
02-08.txt TLE
02-09.txt TLE
02-10.txt TLE
02-11.txt TLE
02-12.txt TLE
sample-01.txt AC 2 ms 2560 KB
sample-02.txt AC 2 ms 2560 KB