oj.uz

Submission #537815

# Submission time Handle Problem Language Result Execution time Memory
537815 2022-03-15T15:20:49 Z new_acc Cities (BOI16_cities) C++14
74 / 100
 6000 ms 47152 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});
	}
	set<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]);
		}
		ss.clear();
		for(int j=1;j<=n;j++) ss.insert({dp[i][j],j});
		while(ss.size()){
			auto it=ss.begin();
			pair<ll,int> v=*it;
			ss.erase(it);
			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.insert({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:48:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |    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 2772 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1488 ms 30444 KB Output is correct
2 Correct 1661 ms 31800 KB Output is correct
3 Correct 581 ms 19808 KB Output is correct
4 Correct 1008 ms 22856 KB Output is correct
5 Correct 624 ms 27344 KB Output is correct
6 Correct 490 ms 22692 KB Output is correct
7 Correct 8 ms 2900 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3088 KB Output is correct
2 Correct 11 ms 3084 KB Output is correct
3 Correct 7 ms 3032 KB Output is correct
4 Correct 10 ms 3040 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3597 ms 36732 KB Output is correct
2 Correct 3682 ms 38012 KB Output is correct
3 Correct 1163 ms 26116 KB Output is correct
4 Correct 2631 ms 30172 KB Output is correct
5 Correct 2197 ms 24784 KB Output is correct
6 Correct 2199 ms 24348 KB Output is correct

Subtask #5
0 / 26.0

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