oj.uz

답안 #939781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939781 2024-03-06T18:22:21 Z mansur Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 371 ms 82444 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 1e6 + 1, mod = 1e9 + 7;

const ll inf = 1e18;
 
double eps = 1e-15;
                                                
bool flg = 0;

vector<pll> g[N];
ll d[4][N];

void djk(int x, int tp) {
	set<pll> s;
	d[tp][x] = 0;
	s.insert({0, x});
	while (sz(s)) {
		x = (*s.begin()).s;
		s.erase(s.begin());
		for (auto [to, w]: g[x]) {
			if (d[tp][to] <= d[tp][x] + w) continue;
			s.erase({d[tp][to], to});
			d[tp][to] = d[tp][x] + w;
			s.insert({d[tp][to], to});
		}
	}
}

vector<int> gr[N], was(N), ord;

void dfs(int u) {
    was[u] = 1;
    for (int to: gr[u]) {
        if (!was[to]) dfs(to);
    }	
    ord.push_back(u);
}	

void slv() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 4; j++)
			d[j][i] = inf;
	}
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	int a[m + 1], b[m + 1], c[m + 1];
	for (int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		g[a[i]].push_back({b[i], c[i]});
		g[b[i]].push_back({a[i], c[i]});
	}
	djk(s, 0);
	djk(t, 1);
	djk(u, 2);
	djk(v, 3);
	ll L = d[0][t];
	for (int i = 1; i <= m; i++) {
		if (d[0][a[i]] + d[1][b[i]] + c[i] == L) {
		    //cout << a[i] << ' ' << b[i] << '\n';
			gr[b[i]].push_back(a[i]);
		}
		if (d[0][b[i]] + d[1][a[i]] + c[i] == L) {
		    //cout << b[i] << ' ' << a[i] << '\n';
			gr[a[i]].push_back(b[i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (sz(gr[i]) && !was[i]) dfs(i);
	}
	//cout << '\n';
	vector<ll> dp1(n + 1, inf), dp2(n + 1, inf);
	ll ans = d[2][v];
	for (int x: ord) {
		dp1[x] = d[2][x];
		dp2[x] = d[3][x];
		for (int to: gr[x]) {
			dp1[x] = min(dp1[x], dp1[to]);
			dp2[x] = min(dp2[x], dp2[to]);
		}
		//cout << x << ' ' << dp1[x] << ' ' << dp2[x] << '\n';
		ans = min(ans, d[3][x] + dp1[x]);
		ans = min(ans, d[2][x] + dp2[x]);
	}
	cout << ans;
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {
		//cout << "Case #" << cur++ << ": ";
		slv();
	}
}
//wenomechainsama

Compilation message

commuter_pass.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main() {
      | ^~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 81168 KB Output is correct
2 Correct 289 ms 80468 KB Output is correct
3 Correct 295 ms 82316 KB Output is correct
4 Correct 297 ms 80636 KB Output is correct
5 Correct 270 ms 80468 KB Output is correct
6 Correct 367 ms 80612 KB Output is correct
7 Correct 270 ms 80468 KB Output is correct
8 Correct 289 ms 80548 KB Output is correct
9 Correct 310 ms 80432 KB Output is correct
10 Correct 240 ms 80620 KB Output is correct
11 Correct 87 ms 74144 KB Output is correct
12 Correct 350 ms 80292 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 81152 KB Output is correct
2 Correct 364 ms 80916 KB Output is correct
3 Correct 359 ms 80520 KB Output is correct
4 Correct 316 ms 81444 KB Output is correct
5 Correct 339 ms 81180 KB Output is correct
6 Correct 305 ms 82444 KB Output is correct
7 Correct 305 ms 81228 KB Output is correct
8 Correct 316 ms 80932 KB Output is correct
9 Correct 354 ms 81212 KB Output is correct
10 Correct 320 ms 79928 KB Output is correct
11 Correct 89 ms 76504 KB Output is correct
12 Correct 298 ms 82328 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 61532 KB Output is correct
2 Correct 15 ms 60252 KB Output is correct
3 Correct 16 ms 60248 KB Output is correct
4 Correct 23 ms 63280 KB Output is correct
5 Correct 18 ms 61532 KB Output is correct
6 Correct 14 ms 59996 KB Output is correct
7 Correct 14 ms 60248 KB Output is correct
8 Correct 15 ms 60252 KB Output is correct
9 Correct 16 ms 60252 KB Output is correct
10 Correct 19 ms 61532 KB Output is correct
11 Correct 15 ms 59992 KB Output is correct
12 Correct 13 ms 59996 KB Output is correct
13 Correct 13 ms 59924 KB Output is correct
14 Correct 14 ms 59996 KB Output is correct
15 Correct 13 ms 59924 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 81168 KB Output is correct
2 Correct 289 ms 80468 KB Output is correct
3 Correct 295 ms 82316 KB Output is correct
4 Correct 297 ms 80636 KB Output is correct
5 Correct 270 ms 80468 KB Output is correct
6 Correct 367 ms 80612 KB Output is correct
7 Correct 270 ms 80468 KB Output is correct
8 Correct 289 ms 80548 KB Output is correct
9 Correct 310 ms 80432 KB Output is correct
10 Correct 240 ms 80620 KB Output is correct
11 Correct 87 ms 74144 KB Output is correct
12 Correct 350 ms 80292 KB Output is correct
13 Correct 317 ms 81152 KB Output is correct
14 Correct 364 ms 80916 KB Output is correct
15 Correct 359 ms 80520 KB Output is correct
16 Correct 316 ms 81444 KB Output is correct
17 Correct 339 ms 81180 KB Output is correct
18 Correct 305 ms 82444 KB Output is correct
19 Correct 305 ms 81228 KB Output is correct
20 Correct 316 ms 80932 KB Output is correct
21 Correct 354 ms 81212 KB Output is correct
22 Correct 320 ms 79928 KB Output is correct
23 Correct 89 ms 76504 KB Output is correct
24 Correct 298 ms 82328 KB Output is correct
25 Correct 18 ms 61532 KB Output is correct
26 Correct 15 ms 60252 KB Output is correct
27 Correct 16 ms 60248 KB Output is correct
28 Correct 23 ms 63280 KB Output is correct
29 Correct 18 ms 61532 KB Output is correct
30 Correct 14 ms 59996 KB Output is correct
31 Correct 14 ms 60248 KB Output is correct
32 Correct 15 ms 60252 KB Output is correct
33 Correct 16 ms 60252 KB Output is correct
34 Correct 19 ms 61532 KB Output is correct
35 Correct 15 ms 59992 KB Output is correct
36 Correct 13 ms 59996 KB Output is correct
37 Correct 13 ms 59924 KB Output is correct
38 Correct 14 ms 59996 KB Output is correct
39 Correct 13 ms 59924 KB Output is correct
40 Correct 336 ms 81848 KB Output is correct
41 Correct 334 ms 80640 KB Output is correct
42 Correct 371 ms 80620 KB Output is correct
43 Correct 95 ms 77004 KB Output is correct
44 Correct 115 ms 77516 KB Output is correct
45 Correct 303 ms 81332 KB Output is correct
46 Correct 273 ms 81572 KB Output is correct
47 Correct 302 ms 80516 KB Output is correct
48 Correct 95 ms 75992 KB Output is correct
49 Correct 299 ms 81856 KB Output is correct
50 Correct 242 ms 80520 KB Output is correct
51 Correct 237 ms 81428 KB Output is correct