oj.uz

Submission #209311

# Submission time Handle Problem Language Result Execution time Memory
209311 2020-03-13T16:52:16 Z AQT Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 2168 KB 
#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<int> graph[205]; 
vector<int> rgraph[205];
int u[50005], v[50005], p[2][50005];
bool used[50005];
long long dist[2][205], cst[50005], rev[50005], rdist[2][205];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dijkstra(int s, int t){
	for(int i = 1; i<=N; i++){
		dist[t][i] = LLONG_MAX>>4;
	}
	dist[t][s] = 0;
	pq.push({0, s});
	while(pq.size()){
		auto pii = pq.top();
		pq.pop();
		if(dist[t][pii.second] != pii.first){
			continue;
		}
		int n = pii.second;
		for(int e : graph[n]){
			if(u[e] == n && dist[t][v[e]] > dist[t][u[e]] + cst[e]){
				dist[t][v[e]] = dist[t][u[e]] + cst[e];
				p[t][v[e]] = e;
				pq.push({dist[t][v[e]], v[e]});
			}
		}
	}
}

void rdijkstra(int s, int t){
	for(int i = 1; i<=N; i++){
		rdist[t][i] = LLONG_MAX>>4;
	}
	rdist[t][s] = 0;
	pq.push({0, s});
	while(pq.size()){
		auto pii = pq.top();
		pq.pop();
		if(rdist[t][pii.second] != pii.first){
			continue;
		}
		int n = pii.second;
		for(int e : rgraph[n]){
			if(rdist[t][u[e]] > rdist[t][v[e]] + cst[e]){
				rdist[t][u[e]] = rdist[t][v[e]] + cst[e];
				//p[t][u[e]] = u[e];
				pq.push({rdist[t][u[e]], u[e]});
			}
		}
	}
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i<=M; i++){
		cin >> u[i] >> v[i] >> cst[i] >> rev[i];
		graph[u[i]].push_back(i);
		rgraph[v[i]].push_back(i);
	}
	dijkstra(1, 0);
	dijkstra(N, 1);
	rdijkstra(1, 0);
	rdijkstra(N, 1);
	long long ans = dist[0][N] + dist[1][1];
	int crnt = N;
	while(p[0][crnt] && crnt != 1){
		used[p[0][crnt]] = 1;
		crnt = u[p[0][crnt]];
	}
	crnt = 1;
	while(p[1][crnt] && crnt != N){
		used[p[1][crnt]] = 1;
		crnt = u[p[1][crnt]];
	}
	for(int e = 1; e<=M; e++){
		if(!used[e]){
			ans = min(ans, dist[0][N] + dist[1][v[e]] + rdist[0][u[e]] + cst[e] + rev[e]);
			ans = min(ans, dist[1][1] + dist[0][v[e]] + rdist[1][u[e]] + cst[e] + rev[e]);		
		}
	}
	for(int e = 1; e<=M; e++){
		//if(used[e]){
			swap(u[e], v[e]);
			graph[u[e]].push_back(e);
			dijkstra(1, 0);
			dijkstra(N, 1);
			graph[u[e]].pop_back();
			swap(u[e], v[e]);
			ans = min(ans, dist[0][N] + dist[1][1] + rev[e]);
		//}
	}
	if(ans >= LLONG_MAX>>4){
		ans = -1;
	}
	cout << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 57 ms 376 KB Output is correct
4 Correct 64 ms 376 KB Output is correct
5 Correct 19 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 95 ms 376 KB Output is correct
11 Correct 85 ms 496 KB Output is correct
12 Correct 89 ms 492 KB Output is correct
13 Correct 31 ms 504 KB Output is correct
14 Correct 42 ms 376 KB Output is correct
15 Correct 37 ms 376 KB Output is correct
16 Correct 41 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 2168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Execution timed out 1096 ms 1784 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 57 ms 376 KB Output is correct
4 Correct 64 ms 376 KB Output is correct
5 Correct 19 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 95 ms 376 KB Output is correct
11 Correct 85 ms 496 KB Output is correct
12 Correct 89 ms 492 KB Output is correct
13 Correct 31 ms 504 KB Output is correct
14 Correct 42 ms 376 KB Output is correct
15 Correct 37 ms 376 KB Output is correct
16 Correct 41 ms 376 KB Output is correct
17 Execution timed out 1095 ms 2168 KB Time limit exceeded
18 Halted 0 ms 0 KB -