Submission #5942582


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

const int N = 10;
bool visited[N];
vector<ll> vals;
ll cost[N][N];
int n, j;

void dfs(int i, ll s) {
	visited[i] = true;
	int outs = 0;
	for (int t = 0; t < n; ++t) {
		if (! visited[t]) {
			++outs;
			dfs(t, s + cost[i][t]);
		}
	}
	if (outs == 0 && i >= j) vals.push_back(s);
	visited[i] = false;
}

ll works() {
	for (j = 0; j < n; ++j) dfs(j, 0);
	sort(vals.begin(), vals.end());
	ll ans = vals.back();

	for (int i = 0; i+1 < vals.size(); ++i) {
		if (vals[i] == vals[i+1]) return -1;
	}
	vals.clear();
	return ans;
}

int main() {
        vector<vector<int>> xr = {
        {1},
        {1,2},
        {1,2,4},
        {1,2,4,7},
        {1,2,4,7,12},
        {1,2,4,8,13,18},
        {1,2,4,8,14,19,24},
        {1,2,4,8,15,24,29,34},
        {1,2,4,8,15,24,29,34,46}
	};

	int m;
	cin >> m;
	for (int i = 1; i < m; ++i) {
		n = i;
		ll b = works() + 1;
		if (b == -1) return 1;

		for (j = 0; j < n; ++j) {
			cost[i][j] = b * xr[i-1][j];
			cost[j][i] = cost[i][j];
		}
	}

	n = m;
	ll res = works();
	if (res == -1) return 1;
	cerr << res << '\n';

	for (int i = 0; i < n; ++i) {
		for (j = 0; j < n; ++j) {
			cout << cost[i][j] << ' ';
		}
		cout << '\n';
	}
}

Submission Info

Submission Time
Task F - Diverta City
User mangolassi
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1378 Byte
Status
Exec Time 351 ms
Memory 17128 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 900 / 900 in1.txt, in2.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
in1.txt 1 ms 256 KB
in2.txt 1 ms 256 KB
in3.txt 1 ms 256 KB
in4.txt 2 ms 256 KB
in5.txt 5 ms 640 KB
in6.txt 34 ms 2420 KB
in7.txt 351 ms 17128 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB