oj.uz

Submission #244299

# Submission time Handle Problem Language Result Execution time Memory
244299 2020-07-03T14:33:14 Z pit4h Olympic Bus (JOI20_ho_t4) C++14
11 / 100
 151 ms 4216 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 201, M = 5e4+1;
const long long INF = 1e12+1;
int n, m, u[M], v[M];
long long c[M], d[M];
long long G[N][N], W[N][N], E[N][N][2];
long long skip[N][N][2], skipt[N][N][2]; // 0 -> (n, 1), 1 -> (1, n)

void calculate_skip(int p, int q) {
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			skip[i][j][p==1] = INF;
		}
	}
	//calc skip here

	for(int k=1; k<=n; ++k) {
		if(k==q) continue;
		vector<bool> vis(n+1);
		vis[k] = 1;
		priority_queue<pair<long long, int>> Q;
		Q.push({0, q});
		skip[q][k][p==1] = 0;
		while(Q.size()) {
			auto cur = Q.top();
			cur.first *= -1;
			Q.pop();
			if(vis[cur.second]) continue;
			vis[cur.second] = 1;

			for(int i=1; i<=n; ++i) {
				if(i==k) continue;
				if(skip[i][k][p==1] > cur.first + W[i][cur.second]) {
					Q.push({-(cur.first + W[i][cur.second]), i});
					skip[i][k][p==1] = cur.first + W[i][cur.second];
				}
			}
		}
	}

	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			skipt[i][j][p==1] = INF;
		}
	}
	//calc skip here

	for(int k=1; k<=n; ++k) {
		if(k==q) continue;
		vector<bool> vis(n+1);
		vis[k] = 1;
		priority_queue<pair<long long, int>> Q;
		Q.push({0, q});
		skipt[q][k][p==1] = 0;
		while(Q.size()) {
			auto cur = Q.top();
			cur.first *= -1;
			Q.pop();
			if(vis[cur.second]) continue;
			vis[cur.second] = 1;

			for(int i=1; i<=n; ++i) {
				if(i==k) continue;
				if(skipt[i][k][p==1] > cur.first + W[cur.second][i]) {
					Q.push({-(cur.first + W[cur.second][i]), i});
					skipt[i][k][p==1] = cur.first + W[cur.second][i];
				}
			}
		}
	}
}

long long solve(int p, int q) {

	long long ans = INF;

	for(int i=0; i<m; ++i) {

		long long path[2] = {0, 0};
// skipt[v[i]][u[i]][p==1]
		path[1] = G[q][v[i]] + c[i] + d[i] + G[u[i]][p];
		path[0] = INF;
		
		path[0] = min(path[0], G[p][v[i]] + c[i] + G[u[i]][q]);

		if(E[u[i]][v[i]][0] != c[i]) {
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][0] + G[v[i]][q]);
		}
		else {
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][1] + G[v[i]][q]);
		}

		if(G[p][u[i]] + c[i] + G[v[i]][q] > G[p][q]) path[0] = min(path[0], G[p][q]);

		else {
			path[0] = min(path[0], skip[p][u[i]][p==1]);
			for(int k=1; k<=n; ++k) {
				if(k != u[i] && k != v[i]) {
					path[0] = min(path[0], G[p][u[i]] + W[u[i]][k] + skip[k][u[i]][p==1]);
				}
			}
		}

		ans = min(ans, path[0] + path[1]);
	}
	return ans;
}

int main() {

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;

	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			G[i][j] = INF;
			W[i][j] = INF;
			E[i][j][0] = E[i][j][1] = INF;
		}
		G[i][i] = 0;
	}

	for(int i=0; i<m; ++i) {
		cin>>u[i]>>v[i]>>c[i]>>d[i];
		G[u[i]][v[i]] = min(G[u[i]][v[i]], c[i]);
		W[u[i]][v[i]] = min(W[u[i]][v[i]], c[i]);
		if(E[u[i]][v[i]][0] > c[i]) {
			E[u[i]][v[i]][1] = E[u[i]][v[i]][0];
			E[u[i]][v[i]][0] = c[i];
		}
		else if(E[u[i]][v[i]][1] > c[i]) {
			E[u[i]][v[i]][1] = c[i];
		}
	}

	for(int k=1; k<=n; ++k) {
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				G[i][j] = min(G[i][j], G[i][k] + G[k][j]);	
			}
		}
	}
	
	calculate_skip(1, n);
	calculate_skip(n, 1);

	long long ans = min({G[1][n]+G[n][1], solve(1, n), solve(n, 1)});
	if(ans >= INF) cout<<-1;
	else cout<<ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2940 KB Output is correct
2 Correct 23 ms 2944 KB Output is correct
3 Correct 75 ms 2936 KB Output is correct
4 Correct 81 ms 2936 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 27 ms 2936 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4216 KB Output is correct
2 Correct 141 ms 4088 KB Output is correct
3 Correct 151 ms 4092 KB Output is correct
4 Correct 77 ms 2944 KB Output is correct
5 Correct 65 ms 2816 KB Output is correct
6 Correct 35 ms 2944 KB Output is correct
7 Correct 16 ms 2816 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 82 ms 4088 KB Output is correct
10 Correct 87 ms 4088 KB Output is correct
11 Correct 111 ms 4088 KB Output is correct
12 Correct 111 ms 4088 KB Output is correct
13 Correct 113 ms 4216 KB Output is correct
14 Correct 108 ms 4088 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2944 KB Output is correct
2 Correct 32 ms 2936 KB Output is correct
3 Correct 116 ms 3960 KB Output is correct
4 Correct 27 ms 2944 KB Output is correct
5 Correct 129 ms 4088 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2940 KB Output is correct
2 Correct 23 ms 2944 KB Output is correct
3 Correct 75 ms 2936 KB Output is correct
4 Correct 81 ms 2936 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 27 ms 2936 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -