oj.uz

Submission #981177

# Submission time Handle Problem Language Result Execution time Memory
981177 2024-05-13T01:17:42 Z penguin133 Robot (JOI21_ho_t4) C++17
24 / 100
 938 ms 127880 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
vector <pii> adj[200005];
map <int, int> mp[200005];
bool precmp[200005];
map <int, int> dist[200005];
map <int, vector <int> > bruh[200005];

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int a, b, c, d; cin >> a >> b >> c >> d;
		mp[a][c]++; mp[b][c]++;
		adj[a].push_back({b, {c, d}});
		adj[b].push_back({a, {c, d}});
		bruh[a][c].push_back(b);
		bruh[b][c].push_back(a);
	}
	priority_queue <pii, vector <pii>, greater <pii> > pq;
	dist[1][0] = 0;
	pq.push({0, {1, 0}});
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se.fi, z = pq.top().se.se; pq.pop();
		if(dist[y][z] < x)continue;
		if(y == n){
			cout << x;
			return;
		}
		if(!precmp[y]){
			precmp[y] = 1;
			mp[y][z]--;
			for(auto i : adj[y]){
				int cst = 0;
				if(1){
					cst = i.se.se;
					if(dist[i.fi].find(i.se.fi) == dist[i.fi].end() || dist[i.fi][i.se.fi] > x + cst){
						dist[i.fi][i.se.fi] = x + cst;
						pq.push({x + cst, {i.fi, i.se.fi}});
					}
				}
				if(mp[y][i.se.fi] <= 1){
					if(dist[i.fi].find(0) == dist[i.fi].end() || dist[i.fi][0] > x){
						dist[i.fi][0] = x;
						//cout << y << ' ' << z << ' ' << x << ' ' << i.fi << ' ' << 0 << '\n';
						pq.push({x, {i.fi, 0}});
					}
				}
			}
			mp[y][z]++;
		}
		if(bruh[y][z].size() == 2){
			for(auto i : bruh[y][z]){
				if(dist[i].find(0) == dist[i].end() || dist[i][0] > x){
					//cout << x << ' ' << i << ' ' << 0 << '\n';
					dist[i][0] = x;
					pq.push({x, {i, 0}});
				}
			}
		}
	}
	int ans = 1e18;
	for(auto [i, j] : dist[n]){
		//cout << i << ' ' << j << '\n';
		ans = min(ans, j);
	}
	cout << (ans == 1e18 ? -1 : ans);
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

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

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 7 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33300 KB Output is correct
7 Incorrect 8 ms 33628 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 60168 KB Output is correct
2 Correct 77 ms 47512 KB Output is correct
3 Correct 109 ms 53840 KB Output is correct
4 Correct 80 ms 49928 KB Output is correct
5 Correct 938 ms 127880 KB Output is correct
6 Correct 766 ms 110028 KB Output is correct
7 Correct 261 ms 73108 KB Output is correct
8 Correct 351 ms 78360 KB Output is correct
9 Correct 331 ms 78608 KB Output is correct
10 Correct 303 ms 77684 KB Output is correct
11 Correct 116 ms 54164 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33372 KB Output is correct
2 Correct 7 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33372 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 7 ms 33300 KB Output is correct
7 Incorrect 8 ms 33628 KB Output isn't correct
8 Halted 0 ms 0 KB -