oj.uz

Submission #670957

# Submission time Handle Problem Language Result Execution time Memory
670957 2022-12-11T13:49:32 Z dozer Cities (BOI16_cities) C++14
74 / 100
 6000 ms 257212 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define M 40
#define int long long

int arr[N], dist[N][M], flag[N];
pii ind[N * M];
int rev[N][M];
vector<pii> adj[N];

const int INF = 1e18 + 7;

int32_t main()
{
	#ifndef ONLINE_JUDGE
	//fileio();
	#endif
	fastio();

 	int n, m, k;
 	cin>>n>>k>>m;
 	for (int i = 1; i <= k; i++)
 	{
 		int node;
 		cin>>node;
 		flag[node] = 1;
 		arr[node] = i - 1;
 	}

 	for (int i = 1; i <= m; i++)
 	{
 		int u, v, w;
 		cin>>u>>v>>w;
 		adj[u].pb({v, w});
 		adj[v].pb({u, w});
 	}

 	int cntr = 1;
 	for (int i = 1; i <= n; i++) 
 	{
 		for (int j = 0; j < (1<<k); j++) 
 		{
 			dist[i][j] = INF;
 			ind[cntr] = {i, j};
 			rev[i][j] = cntr;
 			cntr++;
 		}
 	}

 	priority_queue<pii> q;
 	for (int i = 1; i <= n; i++)
 	{
 		if (flag[i]) 
 		{
 			q.push({0, rev[i][(1<<arr[i])]});
 			dist[i][(1<<arr[i])] = 0;
 		}
 	}

 	int steps = 0;
 	while(!q.empty())
 	{
 		pii tmp = q.top();
 		q.pop();
 		int x = tmp.nd;
 		int top = ind[x].st, mask = ind[x].nd, d = -tmp.st;
 		if (d != dist[top][mask]) continue;
 		int comp = ((1<<k) - 1) ^ mask;
 		for (auto i : adj[top])
 		{
 			int v = i.st, w = i.nd;
 			int tmpo = 0;
 			for (int j = comp; j > 0; j = (j - 1) & comp)
 			{
 				steps++;
 				tmpo++;
 				int gh = mask | j;
 				if (dist[v][gh] > w + d + dist[v][j])
 				{
 					dist[v][gh] = w + d + dist[v][j];
 					q.push({-dist[v][gh], rev[v][gh]});
 				}
 			}
 			int gh = mask;
 			if (dist[v][gh] > w + d)
			{
				dist[v][gh] = w + d;
				q.push({-dist[v][gh], rev[v][gh]});
			}
 		}
 	}
 	int ans = INF;
 	for (int i = 1; i <= n; i++)
 	{
 		ans = min(ans, dist[i][(1<<k) - 1]);
 	}
 	cout<<ans<<endl;
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 104856 KB Output is correct
2 Correct 939 ms 103820 KB Output is correct
3 Correct 495 ms 87252 KB Output is correct
4 Correct 76 ms 13444 KB Output is correct
5 Correct 436 ms 86052 KB Output is correct
6 Correct 59 ms 12744 KB Output is correct
7 Correct 5 ms 3796 KB Output is correct
8 Correct 4 ms 3540 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4256 KB Output is correct
2 Correct 9 ms 4308 KB Output is correct
3 Correct 7 ms 3796 KB Output is correct
4 Correct 7 ms 3796 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2903 ms 166396 KB Output is correct
2 Correct 3107 ms 165592 KB Output is correct
3 Correct 1628 ms 112124 KB Output is correct
4 Correct 1945 ms 90024 KB Output is correct
5 Correct 390 ms 36868 KB Output is correct
6 Correct 112 ms 16504 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6100 ms 257212 KB Time limit exceeded
2 Halted 0 ms 0 KB -