oj.uz

Submission #855802

# Submission time Handle Problem Language Result Execution time Memory
855802 2023-10-01T20:45:15 Z Hakiers Robot (JOI21_ho_t4) C++17
0 / 100
 3000 ms 333220 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
const ll oo = 1e18;
vector<tuple<int, int, int>> G[MAXN];
map<int, long long> mapa[MAXN];
map<int, long long> cost[MAXN][2];

void connect(int a, int b, int c, int h){
	G[a].push_back({b, c, h});
	G[b].push_back({a, c, h});
	

	cost[a][0][c] = oo;
	cost[a][1][c] = oo;
	cost[b][0][c] = oo;
	cost[b][1][c] = oo;
	
	mapa[a][c];
	mapa[b][c];
	
	mapa[a][c] += h;
	mapa[b][c] += h;

}

void dijkstra(){
	priority_queue<tuple<long long, int, int, int, pair<int, int>>> Q;
	Q.push({0, 1, 0, 0, {-1, 0}});
	
	cost[1][0][0] = oo;
	while(Q.size()){
		auto [d, v, krawedz, plac, in] = Q.top();
		Q.pop();
		
		if(cost[v][plac][krawedz] <= -d) continue;
		cost[v][plac][krawedz] = -d;
		
		
		for(auto [u, c, h] : G[v]){
			ll actcost;
			
			//placimy za krawedz
			actcost = h;
			if(cost[u][1][c] > cost[v][plac][krawedz] + actcost)
				Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 1, {c, h}});
			
			//nie placimy za nia
			actcost = mapa[v][c] - h;
			if(c == in.first)
				actcost = max(actcost - (ll)in.second, (ll)0);
			if(cost[u][0][c] > cost[v][plac][krawedz] + actcost)
				Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 0, {0, 0}});
			
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= m; i++){
		int a, b, c, h;
		cin >> a >> b >> c >> h;
		connect(a, b, c, h);
	}
	

		
	dijkstra();
	ll res = oo;
	
	for(auto [u, c, h] : G[n])
		res = min(res, min(cost[n][0][c], cost[n][1][c]));
	
	if(res == oo)
	res = -1;
	
	cout << res << endl;
	

}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16984 KB Output is correct
6 Correct 4 ms 16868 KB Output is correct
7 Correct 11 ms 18136 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 563 ms 83560 KB Output is correct
10 Correct 294 ms 50596 KB Output is correct
11 Correct 6 ms 17500 KB Output is correct
12 Incorrect 8 ms 17500 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 66308 KB Output is correct
2 Correct 137 ms 33988 KB Output is correct
3 Correct 528 ms 63628 KB Output is correct
4 Correct 204 ms 35684 KB Output is correct
5 Execution timed out 3033 ms 333220 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16984 KB Output is correct
6 Correct 4 ms 16868 KB Output is correct
7 Correct 11 ms 18136 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 563 ms 83560 KB Output is correct
10 Correct 294 ms 50596 KB Output is correct
11 Correct 6 ms 17500 KB Output is correct
12 Incorrect 8 ms 17500 KB Output isn't correct
13 Halted 0 ms 0 KB -