oj.uz

Submission #485507

# Submission time Handle Problem Language Result Execution time Memory
485507 2021-11-08T03:06:25 Z hohohaha Cities (BOI16_cities) C++14
100 / 100
 3084 ms 51280 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;
const int maxn = 2e5 + 5, inf = LLONG_MAX / 1000ll; 
int n,m; 
vector<ii> g[maxn]; 
int dp[maxn][1 << 5];  

void solve() {
	int k; vector<int> imp; 
	cin >> n >> k >> m; fori(i, 0, k - 1) { int t; cin >> t; imp.eb(t); }
	fori(i, 1, m) {
		int u, v, w; cin >> u >> v >> w;
		g[u].eb(v, w); 
		g[v].eb(u, w); 
	}
	fori(i, 1, n) fori(mas, 0, (1 << k)  - 1) {
		dp[i][mas] = inf; 
	}
	fori(i, 1, n) dp[i][0] = 0; 
	fori(i, 0, k - 1) dp[imp[i]][1 << i] = 0; 
	fori(mas, 1, (1 << k) - 1) { 
		fori(i, 1, n) { 
			for(int mas2 = mas; mas2 > 0; mas2 = (mas2 - 1) & mas) { 
				for(ii j: g[i]) { 
					dp[i][mas] = min(dp[i][mas], dp[j.fi][mas2] + dp[i][mas ^ mas2] + j.se); 
				}
			}
		}
		priority_queue<ii, vector<ii>, greater<ii> > q; 
		fori(i, 1, n) q.em(dp[i][mas], i); 
		while(q.size()) { 
			int d = q.top().fi, i = q.top().se; q.om(); 
			if(d != dp[i][mas]) continue; 
			for(ii j: g[i]) { 
				if(dp[j.fi][mas] > dp[i][mas] + j.se) { 
					dp[j.fi][mas] = dp[i][mas] + j.se; 
					q.em(dp[j.fi][mas], j.fi); 
				}
			}
		}
	}
	int ans = inf; 
	fori(i, 1, n) ans = min(ans, dp[i][(1 << k) - 1]); 
	cout << ans; 
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 46908 KB Output is correct
2 Correct 645 ms 46456 KB Output is correct
3 Correct 449 ms 39008 KB Output is correct
4 Correct 70 ms 14148 KB Output is correct
5 Correct 341 ms 46884 KB Output is correct
6 Correct 63 ms 14148 KB Output is correct
7 Correct 5 ms 5444 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5324 KB Output is correct
2 Correct 7 ms 5444 KB Output is correct
3 Correct 5 ms 5372 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1554 ms 46940 KB Output is correct
2 Correct 1367 ms 50612 KB Output is correct
3 Correct 930 ms 41120 KB Output is correct
4 Correct 842 ms 35880 KB Output is correct
5 Correct 199 ms 21144 KB Output is correct
6 Correct 108 ms 19860 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3044 ms 47036 KB Output is correct
2 Correct 3084 ms 51280 KB Output is correct
3 Correct 2909 ms 50780 KB Output is correct
4 Correct 2090 ms 41284 KB Output is correct
5 Correct 1697 ms 35984 KB Output is correct
6 Correct 405 ms 21752 KB Output is correct
7 Correct 204 ms 19880 KB Output is correct