oj.uz

답안 #827674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827674 2023-08-16T16:15:01 Z NhanBeoo Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 249 ms 20748 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")

#include <bits/stdc++.h>
using namespace std;

#define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;

const int N = 1e5 + 5;
int n, m; 
vii adj[N];
int um[N], vm[N];

vi flood(int s){
	vi dis(n + 1, LLONG_MAX);
	dis[s] = 0;
	priority_queue<ii, vii, greater<ii>> q;
	q.push({0, s});
	while(q.size()){
		auto [len, u] = q.top(); q.pop();
		if(dis[u] != len) continue;
		for(auto [v, w]: adj[u]){
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
	return dis;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	int s, t; cin >> s >> t;
	int u, v; cin >> u >> v;
	while(m--){
		int x, y, z; cin >> x >> y >> z;
		adj[x].push_back({y, z});
		adj[y].push_back({x, z});
	}
	auto S = flood(s), T = flood(t), U = flood(u), V = flood(v);
	vii dag;
	for(int i=1; i<=n; i++){
		if(S[i] + T[i] != S[t]) continue;
		dag.push_back({T[i], i});
	}
	sort(ALL(dag));
	int ans = U[v];
	for(auto [len, x]: dag){
		um[x] = U[x];
		vm[x] = V[x];
		for(auto [y, z]: adj[x]){
			if(T[y] + z == len){
				um[x] = min(um[x], um[y]);
				vm[x] = min(vm[x], vm[y]);
			}
		}
		ans = min(ans, um[x] + V[x]);
		ans = min(ans, vm[x] + U[x]);
	}
	cout << ans;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 19232 KB Output is correct
2 Correct 228 ms 18656 KB Output is correct
3 Correct 205 ms 20748 KB Output is correct
4 Correct 229 ms 19112 KB Output is correct
5 Correct 224 ms 19524 KB Output is correct
6 Correct 195 ms 19384 KB Output is correct
7 Correct 205 ms 19620 KB Output is correct
8 Correct 244 ms 19532 KB Output is correct
9 Correct 198 ms 17976 KB Output is correct
10 Correct 155 ms 17728 KB Output is correct
11 Correct 69 ms 13356 KB Output is correct
12 Correct 208 ms 18020 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 18652 KB Output is correct
2 Correct 201 ms 18744 KB Output is correct
3 Correct 219 ms 18780 KB Output is correct
4 Correct 206 ms 18784 KB Output is correct
5 Correct 213 ms 19356 KB Output is correct
6 Correct 204 ms 19700 KB Output is correct
7 Correct 216 ms 19172 KB Output is correct
8 Correct 223 ms 18832 KB Output is correct
9 Correct 218 ms 19344 KB Output is correct
10 Correct 249 ms 18620 KB Output is correct
11 Correct 67 ms 13632 KB Output is correct
12 Correct 223 ms 19648 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4068 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 12 ms 5332 KB Output is correct
5 Correct 6 ms 4112 KB Output is correct
6 Correct 2 ms 2792 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 7 ms 4052 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 19232 KB Output is correct
2 Correct 228 ms 18656 KB Output is correct
3 Correct 205 ms 20748 KB Output is correct
4 Correct 229 ms 19112 KB Output is correct
5 Correct 224 ms 19524 KB Output is correct
6 Correct 195 ms 19384 KB Output is correct
7 Correct 205 ms 19620 KB Output is correct
8 Correct 244 ms 19532 KB Output is correct
9 Correct 198 ms 17976 KB Output is correct
10 Correct 155 ms 17728 KB Output is correct
11 Correct 69 ms 13356 KB Output is correct
12 Correct 208 ms 18020 KB Output is correct
13 Correct 215 ms 18652 KB Output is correct
14 Correct 201 ms 18744 KB Output is correct
15 Correct 219 ms 18780 KB Output is correct
16 Correct 206 ms 18784 KB Output is correct
17 Correct 213 ms 19356 KB Output is correct
18 Correct 204 ms 19700 KB Output is correct
19 Correct 216 ms 19172 KB Output is correct
20 Correct 223 ms 18832 KB Output is correct
21 Correct 218 ms 19344 KB Output is correct
22 Correct 249 ms 18620 KB Output is correct
23 Correct 67 ms 13632 KB Output is correct
24 Correct 223 ms 19648 KB Output is correct
25 Correct 7 ms 4068 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 12 ms 5332 KB Output is correct
29 Correct 6 ms 4112 KB Output is correct
30 Correct 2 ms 2792 KB Output is correct
31 Correct 2 ms 2772 KB Output is correct
32 Correct 3 ms 2900 KB Output is correct
33 Correct 2 ms 2772 KB Output is correct
34 Correct 7 ms 4052 KB Output is correct
35 Correct 2 ms 2644 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 2 ms 2644 KB Output is correct
39 Correct 2 ms 2644 KB Output is correct
40 Correct 193 ms 18876 KB Output is correct
41 Correct 221 ms 18052 KB Output is correct
42 Correct 194 ms 18064 KB Output is correct
43 Correct 72 ms 14240 KB Output is correct
44 Correct 70 ms 14240 KB Output is correct
45 Correct 234 ms 19408 KB Output is correct
46 Correct 180 ms 19396 KB Output is correct
47 Correct 222 ms 19184 KB Output is correct
48 Correct 74 ms 14252 KB Output is correct
49 Correct 164 ms 18784 KB Output is correct
50 Correct 184 ms 19288 KB Output is correct
51 Correct 174 ms 19444 KB Output is correct