oj.uz

Submission #80847

# Submission time Handle Problem Language Result Execution time Memory
80847 2018-10-22T13:48:24 Z scanhex Cities (BOI16_cities) C++17
100 / 100
 2712 ms 99168 KB 
#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
using ll = long long;
 
nagai oo = 1e18;
 
const int N = 1e5;
 
vector<pair<int, int>> g[N];
 
const int SZ = 32;
 
nagai dp[SZ][N];
 
const int MEM = 200000000;
char arr[MEM];
int ptr = 0;
void* operator new(size_t n)
{
	ptr += n;
	return (void*)(arr + ptr - n);
}
void operator delete(void*){}
 
int cur_layer = 0;
 
struct cmp
{
	bool operator()(int a, int b) const
	{
		if (dp[cur_layer][a] != dp[cur_layer][b])
			return dp[cur_layer][a] > dp[cur_layer][b];
		return a > b;
	}
};
 
priority_queue<pair<nagai, int>> st;
 
bool used[N];
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, m;
	cin >> n >> k >> m;
	vector<int> imp(k);
	for (auto& x : imp)
		cin >> x, --x;
	for (int i = 0; i < m; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	int sz = 1 << k;
	for (int i = 0; i < sz; ++i)
		for (int j = 0; j < n; ++j)
			dp[i][j] = oo;
	for (int i = 0; i < k; ++i)
		dp[1 << i][imp[i]] = 0;
	for (int i = 1; i < sz; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			for (int k = i; k > 0; k = (k - 1) & i)
				dp[i][j] = min(dp[i][j], dp[k][j] + dp[i ^ k][j]);
		}
		cur_layer = i;
		for (int j = 0; j < n; ++j)
			st.push({-dp[i][j], j});
		fill(used, used + n, false);
		while (st.size())
		{
			 pair<nagai, int> px = st.top();
			 st.pop();
			 int x = px.second;
			 if (used[x])
				 continue;
			 used[x] = true;
			 for (auto p : g[x])
			 {
				 if (dp[i][x] + p.second < dp[i][p.first])
				 {
					  dp[i][p.first] = dp[i][x] + p.second;
					  st.push({-dp[i][p.first], p.first});
				 }
			 }
		}
	}
	cout << *min_element(dp[sz - 1], dp[sz - 1] + n) << '\n';
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2920 KB Output is correct
3 Correct 5 ms 2984 KB Output is correct
4 Correct 4 ms 3080 KB Output is correct
5 Correct 4 ms 3320 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 27576 KB Output is correct
2 Correct 698 ms 31828 KB Output is correct
3 Correct 543 ms 31828 KB Output is correct
4 Correct 100 ms 31828 KB Output is correct
5 Correct 375 ms 38444 KB Output is correct
6 Correct 117 ms 38444 KB Output is correct
7 Correct 7 ms 38444 KB Output is correct
8 Correct 6 ms 38444 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 38444 KB Output is correct
2 Correct 9 ms 38444 KB Output is correct
3 Correct 8 ms 38444 KB Output is correct
4 Correct 8 ms 38444 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1320 ms 55732 KB Output is correct
2 Correct 1268 ms 60068 KB Output is correct
3 Correct 936 ms 60068 KB Output is correct
4 Correct 729 ms 60068 KB Output is correct
5 Correct 201 ms 60068 KB Output is correct
6 Correct 93 ms 60068 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2628 ms 90552 KB Output is correct
2 Correct 2712 ms 94752 KB Output is correct
3 Correct 2555 ms 99168 KB Output is correct
4 Correct 1765 ms 99168 KB Output is correct
5 Correct 1355 ms 99168 KB Output is correct
6 Correct 321 ms 99168 KB Output is correct
7 Correct 118 ms 99168 KB Output is correct