oj.uz

Submission #422688

# Submission time Handle Problem Language Result Execution time Memory
422688 2021-06-10T10:22:44 Z Maqsut_03 Cities (BOI16_cities) C++14
0 / 100
 10 ms 392 KB 
#include <iostream>
#include <fstream>
#include <cmath>
#include <random>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <functional>
#include <typeinfo>

#include <vector>
#include <array>
#include <valarray>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>

#define ll long long
#define ff first
#define ss second
#define sz size()
const int M = 1e9+7, N = 50;
using namespace std;

int n, m, k, a[10];
ll ans = M, ans0 = 0, ans1;
vector<pair<ll, ll> > g[N];
bool used[N], used2[N], used3[N];

void dfs(int v, int u, ll s)
{
	used[v] = 1;
	if (v == u && ans > s)
	{
		ans = s;
		for (int i=1; i<=n; i++) used2[i] = used[i];
		used[v] = 0;
		return ;
	}
	for (auto [x, y]:g[v])
	{
		if (!used[x]) dfs(x, u, s + y);
	}
	used[v] = 0;
}


void dfs2(int v, int u, ll s = 0)
{
	used[v] = 1;
	
	if (v == u && ans > s)
	{
		ans = s;
		for (int i=1; i<=n; i++) used2[i] = used[i];
		used[v] = 0;
		return ;
	}
	
	for (auto [x, y]:g[v])
	{
		if (!used[x]) dfs(x, u, s + y);
	}
	
	used[v] = 0;
}

int main()
{
	cin >> n >> k >> m;
	for (int i=1; i<=k; i++) cin >> a[i];
	int x, y;
	ll z;
	for (int i=1; i<=m; i++)
	{
		cin >> x >> y >> z;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);	
	}
	
	dfs(a[1], a[2], 0);
//	for (int i=1; i<=n; i++) cout << used[i] << " ";
//	cout << "\n";
	ans0 += ans;
	int k0 = 3;
	bool q0 = 1;
	while (k0 <= k)
	{
		if (q0)for (int i=1; i<=n; i++) used[i] |= used2[i];
		else for (int i=1; i<=n; i++) used[i] |= used3[i];
		q0 = 0;
//	for (int i=1; i<=n; i++) cout << used[i] << " ";
//	cout << "\n";
		fill(used2, used2 + N, 0);
		ans1 = M;
		for (int i=1; i<=n; i++)
		{
			ans = M;
			if (used[i])
			{
				dfs2(i, a[k0]);
			}
			if (ans < ans1)
			{
				ans1 = ans;
				for (int i=1; i<=n; i++) used3[i] = used2[i];
			}
		}
		ans0+=ans1;
		k0++;
	}
	cout << ans0;
}

Compilation message

cities.cpp: In function 'void dfs(int, int, long long int)':
cities.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  for (auto [x, y]:g[v])
      |            ^
cities.cpp: In function 'void dfs2(int, int, long long int)':
cities.cpp:67:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |  for (auto [x, y]:g[v])
      |            ^

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 9 ms 204 KB Output is correct
3 Incorrect 10 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -