oj.uz

Submission #678444

# Submission time Handle Problem Language Result Execution time Memory
678444 2023-01-06T02:45:02 Z thanhdanh436 Relay Marathon (NOI20_relaymarathon) C++17
5 / 100
 34 ms 52108 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define file "4special"
using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int inf = INT_MAX;
const long long llinf = LLONG_MAX;
const int lg = 25; // lg + 1

template<class T> bool minimize(T &a, T b) { 
	return a > b ? (a = b, true) : false; 
}
template<class T> bool maximize(T &a, T b) { 
	return a < b ? (a = b, true) : false; 
}
template<class T> bool add(T &a, T b) { 
	a += b; 
	while (a > mod) a -= mod; 
	return true; 
}

int n, m, k;
int g[505][505];
vector<pair<int, int> > adj[N];
int id[N];
bool special[N];

namespace sub1 {
	void floyd(void) {
		for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
			minimize(g[i][j], g[i][k] + g[k][j]);
		}
	}
	void solve(void) {
		floyd();
		int ans = g[0][0];
		for (int a = 1; a <= k; ++a)
		for (int b = 1; b <= k; ++b)
		for (int c = 1; c <= k; ++c)
		for (int d = 1; d <= k; ++d) {
			if (a == b || a == c || a == d || b == c || b == d || c == d) continue;
			int x = id[a], y = id[b], z = id[c], t = id[d];
			if (g[x][y] + g[z][t] < ans && g[x][y] != g[0][0] && g[z][t] != g[0][0]) 
				minimize(ans, g[x][y] + g[z][t]);
		}
		cout << ans;
	}	
}

namespace full {
	int d[N], from[N];
	typedef pair<int, int> node;
	pair<int, pair<int, int> > dijkstra_special(void) { // from special to another
		memset(d, 0x3f, sizeof d);
		memset(from, 0, sizeof from);
		priority_queue<node, vector<node>, greater<node> > q;
		for (int i = 1; i <= n; ++i) {
			if (special[i]) {
				q.push({0, i});
				from[i] = i;
				d[i] = 0;
			}
		}
		while (q.size()) {
			int u = q.top().se; q.pop();
			for (auto i : adj[u]) {
				int v = i.fi, l = i.se;
				if (d[u] + l < d[v]) {
					d[v] = d[u] + l;
					from[v] = from[u];
					q.push({d[v], v});
				}
			}
		}
		int ans = d[0], s = 1, t = 1;
		for (int u = 1; u <= n; ++u) {
			for (auto [v, w] : adj[u]) if (from[u] != from[v]) {
				if (minimize(ans, d[u] + d[v] + w)) s = u, t = v;
			}
		}
		return {ans, {s, t}};
	}	
	pair<int, int> dijstra(int s) { // shortest path from source
		memset(d, 0x3f, sizeof d);
		priority_queue<node, vector<node>, greater<node> > q;
		q.push({0, s});
		d[s] = 0;
		while (q.size()) {
			int u = q.top().se; q.pop();
			if (special[u]) return {d[u], u};
			for (auto i : adj[u]) {
				int v = i.fi, l = i.se;
				if (d[u] + l < d[v]) {
					d[v] = d[u] + l;
					q.push({d[v], v});
				}
			}
		}
		return {inf, 0};
	}
	void solve(void) {
		int dis1, dis2, s1, t1, s2, t2;
		// int ans = inf;
		auto ans1 = dijkstra_special();
		dis1 = ans1.fi, s1 = ans1.se.fi, t1 = ans1.se.se;
		special[s1] = special[t1] = false;
		auto ans2 = dijkstra_special();
		dis2 = ans2.fi, s2 = ans2.se.fi, t2 = ans2.se.se;
		cout << dis1 + dis2;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// freopen(file".inp", "r",stdin);
	// freopen(file".out", "w",stdout);

	cin >> n >> m >> k;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= m; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back({v, c});
		adj[v].push_back({u, c});
		g[u][v] = c;
		g[v][u] = c;
	}

	for (int i = 1; i <= k; ++i) {
		int x;
		cin >> x;
		id[i] = x;
		special[x] = true;
	}

	if (n <= 50) {
		sub1::solve();
		return 0;
	}

	full::solve();

	return 0;
}

Compilation message

RelayMarathon.cpp: In function 'void full::solve()':
RelayMarathon.cpp:114:27: warning: variable 's2' set but not used [-Wunused-but-set-variable]
  114 |   int dis1, dis2, s1, t1, s2, t2;
      |                           ^~
RelayMarathon.cpp:114:31: warning: variable 't2' set but not used [-Wunused-but-set-variable]
  114 |   int dis1, dis2, s1, t1, s2, t2;
      |                               ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25824 KB Output is correct
2 Correct 13 ms 25848 KB Output is correct
3 Correct 14 ms 25812 KB Output is correct
4 Correct 13 ms 25776 KB Output is correct
5 Correct 14 ms 25812 KB Output is correct
6 Correct 14 ms 25800 KB Output is correct
7 Correct 16 ms 25824 KB Output is correct
8 Correct 13 ms 25812 KB Output is correct
9 Correct 16 ms 25928 KB Output is correct
10 Correct 14 ms 25740 KB Output is correct
11 Correct 23 ms 25836 KB Output is correct
12 Correct 18 ms 25832 KB Output is correct
13 Correct 24 ms 25788 KB Output is correct
14 Correct 13 ms 25812 KB Output is correct
15 Correct 29 ms 25900 KB Output is correct
16 Correct 14 ms 25812 KB Output is correct
17 Correct 34 ms 25812 KB Output is correct
18 Correct 13 ms 25760 KB Output is correct
19 Correct 30 ms 25812 KB Output is correct
20 Correct 15 ms 25812 KB Output is correct
21 Correct 21 ms 25812 KB Output is correct
22 Correct 12 ms 25812 KB Output is correct
23 Correct 29 ms 25868 KB Output is correct
24 Correct 18 ms 25740 KB Output is correct
25 Correct 14 ms 25820 KB Output is correct
26 Correct 13 ms 25812 KB Output is correct
27 Correct 14 ms 25796 KB Output is correct
28 Correct 27 ms 25860 KB Output is correct
29 Correct 16 ms 25812 KB Output is correct
30 Correct 16 ms 25904 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25824 KB Output is correct
2 Correct 13 ms 25848 KB Output is correct
3 Correct 14 ms 25812 KB Output is correct
4 Correct 13 ms 25776 KB Output is correct
5 Correct 14 ms 25812 KB Output is correct
6 Correct 14 ms 25800 KB Output is correct
7 Correct 16 ms 25824 KB Output is correct
8 Correct 13 ms 25812 KB Output is correct
9 Correct 16 ms 25928 KB Output is correct
10 Correct 14 ms 25740 KB Output is correct
11 Correct 23 ms 25836 KB Output is correct
12 Correct 18 ms 25832 KB Output is correct
13 Correct 24 ms 25788 KB Output is correct
14 Correct 13 ms 25812 KB Output is correct
15 Correct 29 ms 25900 KB Output is correct
16 Correct 14 ms 25812 KB Output is correct
17 Correct 34 ms 25812 KB Output is correct
18 Correct 13 ms 25760 KB Output is correct
19 Correct 30 ms 25812 KB Output is correct
20 Correct 15 ms 25812 KB Output is correct
21 Correct 21 ms 25812 KB Output is correct
22 Correct 12 ms 25812 KB Output is correct
23 Correct 29 ms 25868 KB Output is correct
24 Correct 18 ms 25740 KB Output is correct
25 Correct 14 ms 25820 KB Output is correct
26 Correct 13 ms 25812 KB Output is correct
27 Correct 14 ms 25796 KB Output is correct
28 Correct 27 ms 25860 KB Output is correct
29 Correct 16 ms 25812 KB Output is correct
30 Correct 16 ms 25904 KB Output is correct
31 Incorrect 20 ms 41436 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 52108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25824 KB Output is correct
2 Correct 13 ms 25848 KB Output is correct
3 Correct 14 ms 25812 KB Output is correct
4 Correct 13 ms 25776 KB Output is correct
5 Correct 14 ms 25812 KB Output is correct
6 Correct 14 ms 25800 KB Output is correct
7 Correct 16 ms 25824 KB Output is correct
8 Correct 13 ms 25812 KB Output is correct
9 Correct 16 ms 25928 KB Output is correct
10 Correct 14 ms 25740 KB Output is correct
11 Correct 23 ms 25836 KB Output is correct
12 Correct 18 ms 25832 KB Output is correct
13 Correct 24 ms 25788 KB Output is correct
14 Correct 13 ms 25812 KB Output is correct
15 Correct 29 ms 25900 KB Output is correct
16 Correct 14 ms 25812 KB Output is correct
17 Correct 34 ms 25812 KB Output is correct
18 Correct 13 ms 25760 KB Output is correct
19 Correct 30 ms 25812 KB Output is correct
20 Correct 15 ms 25812 KB Output is correct
21 Correct 21 ms 25812 KB Output is correct
22 Correct 12 ms 25812 KB Output is correct
23 Correct 29 ms 25868 KB Output is correct
24 Correct 18 ms 25740 KB Output is correct
25 Correct 14 ms 25820 KB Output is correct
26 Correct 13 ms 25812 KB Output is correct
27 Correct 14 ms 25796 KB Output is correct
28 Correct 27 ms 25860 KB Output is correct
29 Correct 16 ms 25812 KB Output is correct
30 Correct 16 ms 25904 KB Output is correct
31 Incorrect 20 ms 41436 KB Output isn't correct
32 Halted 0 ms 0 KB -