oj.uz

Submission #142558

# Submission time Handle Problem Language Result Execution time Memory
142558 2019-08-09T15:25:05 Z DrumpfTheGodEmperor Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 961 ms 48548 KB 
#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef pair<int, int> ii;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5;
struct DPState {
	int stCost = infll, uvCost = infll;
	DPState(int stCost = infll, int uvCost = infll): stCost(stCost), uvCost(uvCost) {};
	bool operator<(const DPState &rhs) const {
		if (stCost == rhs.stCost) return uvCost < rhs.uvCost;
		return stCost < rhs.stCost;
	}
	bool operator!=(const DPState &rhs) const {
		if (stCost != rhs.stCost || uvCost != rhs.uvCost) return true;
		return false;
	}
} dp[N][3];
typedef pair<DPState, ii> iii;
int n, m, s, t, u, v, ans;
vector<ii> g[N];
int distu[N], distv[N];
void djisktra(int src, int (&dist)[N]) {
	memset(dist, 63, sizeof dist);
	dist[src] = 0;
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push(ii(0, src));
	while (!pq.empty()) {
		ii tmp = pq.top(); pq.pop();
		int vertex = tmp.se, cost = tmp.fi;
		if (dist[vertex] != cost) continue;
		fa (i, g[vertex]) {
			int dest = i.fi, edgeCost = i.se;
			if (cost + edgeCost < dist[dest]) {
				dist[dest] = cost + edgeCost;
				pq.push(ii(dist[dest], dest));
			}
		}
	}
}
void solve() {
	fw (i, 0, n) fw (j, 0, 3) dp[i][j] = DPState();
	djisktra(u, distu);
	djisktra(v, distv);
	priority_queue<iii, vector<iii>, greater<iii>> pq;
	pq.push(iii(DPState(0, 0), ii(s, 0)));
	dp[s][0] = DPState(0, 0);
	while (!pq.empty()) {
		iii tmp = pq.top(); pq.pop();
		int state = tmp.se.se, vertex = tmp.se.fi;
		DPState cost = tmp.fi;
		if (cost != dp[vertex][state]) continue; 
		//Change vertexes or change state
		//Change vertex:
		fa (i, g[vertex]) {
			int dest = i.fi, edgeCost = i.se;
			if (DPState(cost.stCost + edgeCost, cost.uvCost) < dp[dest][state]) {
				dp[dest][state] = DPState(cost.stCost + edgeCost, cost.uvCost);
				pq.push(iii(dp[dest][state], ii(dest, state)));
			}
		}
		//Change state
		if (state == 0) {
			if (DPState(cost.stCost, cost.uvCost + distu[vertex]) < dp[vertex][1]) {
				dp[vertex][1] = DPState(cost.stCost, cost.uvCost + distu[vertex]);
				pq.push(iii(dp[vertex][1], ii(vertex, 1)));
			}
		} else if (state == 1) {
			if (DPState(cost.stCost, cost.uvCost + distv[vertex]) < dp[vertex][2]) {
				dp[vertex][2] = DPState(cost.stCost, cost.uvCost + distv[vertex]);
				pq.push(iii(dp[vertex][2], ii(vertex, 2)));
			}
		}
	}
	ans = min(ans, dp[t][2].uvCost);
	ans = min(ans, distu[v]);
//	fw (i, 0, n) fw (j, 0, 3) cout << "dp[" << i << "][" << j << "] = " << dp[i][j].stCost << " " << dp[i][j].uvCost << "\n";
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> s >> t >> u >> v;
	s--, t--, u--, v--;
	fw (i, 0, m) {
		int v1, v2, cost;
		cin >> v1 >> v2 >> cost;
		v1--, v2--;
		g[v1].pb(ii(v2, cost));
		g[v2].pb(ii(v1, cost));
	}
	ans = infll;
	solve();
	//Swap u v and do the same thing
	swap(u, v);
	solve();
	cout << ans;
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 38224 KB Output is correct
2 Correct 839 ms 36948 KB Output is correct
3 Correct 891 ms 30940 KB Output is correct
4 Correct 802 ms 37388 KB Output is correct
5 Correct 831 ms 35680 KB Output is correct
6 Correct 844 ms 38788 KB Output is correct
7 Correct 855 ms 36676 KB Output is correct
8 Correct 838 ms 36948 KB Output is correct
9 Correct 887 ms 36500 KB Output is correct
10 Correct 671 ms 31900 KB Output is correct
11 Correct 289 ms 16248 KB Output is correct
12 Correct 840 ms 36664 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 37484 KB Output is correct
2 Correct 887 ms 36120 KB Output is correct
3 Correct 924 ms 36300 KB Output is correct
4 Correct 904 ms 36264 KB Output is correct
5 Correct 899 ms 36272 KB Output is correct
6 Correct 791 ms 31036 KB Output is correct
7 Correct 961 ms 36172 KB Output is correct
8 Correct 899 ms 36276 KB Output is correct
9 Correct 876 ms 36080 KB Output is correct
10 Correct 877 ms 36232 KB Output is correct
11 Correct 263 ms 16348 KB Output is correct
12 Correct 792 ms 31068 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11504 KB Output is correct
2 Correct 11 ms 9080 KB Output is correct
3 Correct 10 ms 9080 KB Output is correct
4 Correct 42 ms 13312 KB Output is correct
5 Correct 21 ms 10872 KB Output is correct
6 Correct 11 ms 9080 KB Output is correct
7 Correct 12 ms 9212 KB Output is correct
8 Correct 13 ms 9228 KB Output is correct
9 Correct 11 ms 9080 KB Output is correct
10 Correct 20 ms 10616 KB Output is correct
11 Correct 10 ms 8952 KB Output is correct
12 Correct 11 ms 8952 KB Output is correct
13 Correct 10 ms 9080 KB Output is correct
14 Correct 10 ms 9080 KB Output is correct
15 Correct 11 ms 9052 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 38224 KB Output is correct
2 Correct 839 ms 36948 KB Output is correct
3 Correct 891 ms 30940 KB Output is correct
4 Correct 802 ms 37388 KB Output is correct
5 Correct 831 ms 35680 KB Output is correct
6 Correct 844 ms 38788 KB Output is correct
7 Correct 855 ms 36676 KB Output is correct
8 Correct 838 ms 36948 KB Output is correct
9 Correct 887 ms 36500 KB Output is correct
10 Correct 671 ms 31900 KB Output is correct
11 Correct 289 ms 16248 KB Output is correct
12 Correct 840 ms 36664 KB Output is correct
13 Correct 937 ms 37484 KB Output is correct
14 Correct 887 ms 36120 KB Output is correct
15 Correct 924 ms 36300 KB Output is correct
16 Correct 904 ms 36264 KB Output is correct
17 Correct 899 ms 36272 KB Output is correct
18 Correct 791 ms 31036 KB Output is correct
19 Correct 961 ms 36172 KB Output is correct
20 Correct 899 ms 36276 KB Output is correct
21 Correct 876 ms 36080 KB Output is correct
22 Correct 877 ms 36232 KB Output is correct
23 Correct 263 ms 16348 KB Output is correct
24 Correct 792 ms 31068 KB Output is correct
25 Correct 29 ms 11504 KB Output is correct
26 Correct 11 ms 9080 KB Output is correct
27 Correct 10 ms 9080 KB Output is correct
28 Correct 42 ms 13312 KB Output is correct
29 Correct 21 ms 10872 KB Output is correct
30 Correct 11 ms 9080 KB Output is correct
31 Correct 12 ms 9212 KB Output is correct
32 Correct 13 ms 9228 KB Output is correct
33 Correct 11 ms 9080 KB Output is correct
34 Correct 20 ms 10616 KB Output is correct
35 Correct 10 ms 8952 KB Output is correct
36 Correct 11 ms 8952 KB Output is correct
37 Correct 10 ms 9080 KB Output is correct
38 Correct 10 ms 9080 KB Output is correct
39 Correct 11 ms 9052 KB Output is correct
40 Correct 809 ms 48548 KB Output is correct
41 Correct 787 ms 37012 KB Output is correct
42 Correct 825 ms 36928 KB Output is correct
43 Correct 333 ms 16508 KB Output is correct
44 Correct 260 ms 16252 KB Output is correct
45 Correct 717 ms 30396 KB Output is correct
46 Correct 766 ms 30464 KB Output is correct
47 Correct 778 ms 37100 KB Output is correct
48 Correct 322 ms 15872 KB Output is correct
49 Correct 717 ms 48208 KB Output is correct
50 Correct 725 ms 30964 KB Output is correct
51 Correct 632 ms 30164 KB Output is correct