oj.uz

Submission #367950

# Submission time Handle Problem Language Result Execution time Memory
367950 2021-02-19T01:20:31 Z rqi Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 75 ms 3948 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define mp make_pair
#define sz(x) (int)(x).size()
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const int mx = 50005;

const ll INF = 1e18;

int N, M;
int U[mx];
int V[mx];
int C[mx];
int D[mx];

vi adj[mx];

vi S = vi{0, 0};
vi spath[2]; //edge list of shortest path

int forbidden = -1; //forbidden edge
ll dist[mx];
ll o_dist[2][2][mx];

pi from[mx];

void genDist(int typ, int disallowed = -1){
	forbidden = disallowed;

	for(int i = 1; i <= N; i++){
		dist[i] = INF;
	}
		
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	dist[S[typ]] = 0;
	pq.push(mp(dist[S[typ]], S[typ]));

	while(sz(pq)){
		int node = pq.top().s;
		pq.pop();

		for(auto u: adj[node]){
			if(u == forbidden) continue;

			int neigh = V[u];
			ll cost = C[u];

			if(dist[neigh] > dist[node]+cost){
				dist[neigh] = dist[node]+cost;
				from[neigh] = mp(node, u);
				pq.push(mp(dist[neigh], neigh));
			}
		}
	}


}

void reverseEdges(){
	for(int i = 1; i <= N; i++){
		adj[i].clear();
	}

	for(int i = 1; i <= M; i++){
		swap(U[i], V[i]);
	}

	for(int i = 1; i <= M; i++){
		adj[U[i]].pb(i);
	}
}

bool spec[mx];

int main(){
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		cin >> U[i] >> V[i] >> C[i] >> D[i];
		adj[U[i]].pb(i);
	}

	S[0] = 1;
	S[1] = N;

	ll ans = 0;

	for(int typ = 0; typ < 2; typ++){
		genDist(typ);
		ans+=dist[S[1-typ]]; //initialize to initial shortest paths

		// for(int i = 1; i <= N; i++){
		// 	cout << i << " " << dist[i] << "\n";
		// }

		//cout << dist[S[1-typ]] << "\n";

		if(dist[S[1-typ]] != INF){
			int curnode = S[1-typ];
			while(curnode != S[typ]){
				spath[typ].pb(from[curnode].s);
				curnode = from[curnode].f;
			}
			reverse(all(spath[typ]));
		}

		for(int i = 1; i <= N; i++){
			o_dist[typ][0][i] = dist[i];
		}
	}

	reverseEdges();

	for(int typ = 0; typ < 2; typ++){
		genDist(typ);

		for(int i = 1; i <= N; i++){
			o_dist[typ][1][i] = dist[i];
		}
	}

	reverseEdges();



	for(int typ = 0; typ < 2; typ++){
		for(auto ed: spath[typ]){
			spec[ed] = 1;
			ll pans = D[ed];
			genDist(0, ed);
			pans+=dist[S[1]];
			genDist(1, ed);
			pans+=dist[S[0]];
			ckmin(ans, pans);
		}
	}

	for(int i = 1; i <= M; i++){
		if(spec[i]) continue;
		ll pans = D[i];
		pans+=min(o_dist[0][0][S[1]], o_dist[0][0][V[i]]+o_dist[1][1][U[i]]+C[i]);
		pans+=min(o_dist[1][0][S[0]], o_dist[1][0][V[i]]+o_dist[0][1][U[i]]+C[i]);
		ckmin(ans, pans);
	}

	if(ans >= INF){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1644 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 3 ms 1644 KB Output is correct
4 Correct 4 ms 1644 KB Output is correct
5 Correct 3 ms 1644 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 1 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 2 ms 1644 KB Output is correct
10 Correct 39 ms 1644 KB Output is correct
11 Correct 37 ms 1772 KB Output is correct
12 Incorrect 37 ms 1664 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3820 KB Output is correct
2 Correct 71 ms 3692 KB Output is correct
3 Correct 75 ms 3948 KB Output is correct
4 Correct 4 ms 1644 KB Output is correct
5 Correct 3 ms 1644 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Incorrect 2 ms 1516 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1644 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 44 ms 3180 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 56 ms 3692 KB Output is correct
6 Correct 1 ms 1644 KB Output is correct
7 Correct 1 ms 1516 KB Output is correct
8 Correct 55 ms 3692 KB Output is correct
9 Correct 56 ms 3692 KB Output is correct
10 Correct 57 ms 3692 KB Output is correct
11 Correct 56 ms 3692 KB Output is correct
12 Correct 56 ms 3692 KB Output is correct
13 Incorrect 1 ms 1516 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1644 KB Output is correct
2 Correct 2 ms 1516 KB Output is correct
3 Correct 3 ms 1644 KB Output is correct
4 Correct 4 ms 1644 KB Output is correct
5 Correct 3 ms 1644 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 1 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 2 ms 1644 KB Output is correct
10 Correct 39 ms 1644 KB Output is correct
11 Correct 37 ms 1772 KB Output is correct
12 Incorrect 37 ms 1664 KB Output isn't correct
13 Halted 0 ms 0 KB -