oj.uz

Submission #537817

# Submission time Handle Problem Language Result Execution time Memory
537817 2022-03-15T15:28:14 Z new_acc Cities (BOI16_cities) C++14
100 / 100
 2455 ms 40788 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const ll INF=1e18;
ll dp[1<<5][N];
vector<pair<int,int>> graf[N];
bitset<N>wyb;
bitset<N>vis;
int num[N];
void solve(){
	int n,k,m;
	cin>>n>>k>>m;
	int last=0;
	for(int i=0,a;i<k;i++){
		cin>>a;
		wyb[a]=1;
		num[a]=i;
		last=a;
	}
	for(int i=1,a,b,c;i<=m;i++){
		cin>>a>>b>>c;
		graf[a].push_back({b,c}),graf[b].push_back({a,c});
	}
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > ss;
	for(int i=1;i<(1<<k);i++){
		vi s;
		for(int wsk=1;wsk<=n;wsk++) dp[i][wsk]=(wyb[wsk] and ((1<<num[wsk])&i)?dp[i-(1<<num[wsk])][wsk]:INF);
		for(int j=0;j<k;j++) if((1<<j)&i) s.push_back(j);
		for(int j=1;j<(1<<s.size())-1;j++){
			int mask=0;
			for(int xd=0;xd<s.size();xd++) if((1<<xd)&j) mask+=(1<<s[xd]);
			for(int wsk=1;wsk<=n;wsk++) dp[i][wsk]=min(dp[i][wsk],dp[mask][wsk]+dp[i^mask][wsk]);
		}
		for(int j=1;j<=n;j++) ss.push({dp[i][j],j});
		while(ss.size()){
			pair<ll,int> v=ss.top();
			ss.pop();
			if(vis[v.se]) continue;
			dp[i][v.se]=v.fi;
			vis[v.se]=1;
			for(auto [u,c]:graf[v.se])
				if(!vis[u]) ss.push({c+v.fi,u});
		}
		vis.reset();
	}
	cout<<dp[(1<<k)-1][last]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message

cities.cpp: In function 'void solve()':
cities.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int xd=0;xd<s.size();xd++) if((1<<xd)&j) mask+=(1<<s[xd]);
      |                 ~~^~~~~~~~~
cities.cpp:46:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |    for(auto [u,c]:graf[v.se])
      |             ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 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 617 ms 17532 KB Output is correct
2 Correct 667 ms 17456 KB Output is correct
3 Correct 303 ms 12992 KB Output is correct
4 Correct 321 ms 11436 KB Output is correct
5 Correct 319 ms 14408 KB Output is correct
6 Correct 204 ms 11324 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 3 ms 2788 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3004 KB Output is correct
2 Correct 7 ms 3028 KB Output is correct
3 Correct 5 ms 2900 KB Output is correct
4 Correct 7 ms 2900 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 23732 KB Output is correct
2 Correct 1244 ms 23800 KB Output is correct
3 Correct 716 ms 19300 KB Output is correct
4 Correct 893 ms 17392 KB Output is correct
5 Correct 634 ms 11864 KB Output is correct
6 Correct 585 ms 13080 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2455 ms 36320 KB Output is correct
2 Correct 2430 ms 40788 KB Output is correct
3 Correct 2447 ms 40692 KB Output is correct
4 Correct 1312 ms 34064 KB Output is correct
5 Correct 1730 ms 28148 KB Output is correct
6 Correct 1230 ms 17076 KB Output is correct
7 Correct 1160 ms 16580 KB Output is correct