oj.uz

Submission #244266

# Submission time Handle Problem Language Result Execution time Memory
244266 2020-07-03T12:46:51 Z pit4h Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 137 ms 3576 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();
			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];
				}
			}
		}
	}
}

long long solve(int p, int q) {

	long long ans = INF;

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

		long long path[2] = {0, 0};
		path[1] = G[q][v[i]] + c[i] + d[i] + G[u[i]][p];
		path[0] = INF;
		
		if(E[u[i]][v[i]][0] != c[i]) {
			path[0] = min(path[0], G[p][u[i]] + E[u[i]][v[i]][0] + skip[v[i]][u[i]][p==1]);
		}
		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]] + W[u[i]][v[i]] + G[v[i]][q] > G[p][q]) 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 42 ms 2304 KB Output is correct
2 Correct 19 ms 2304 KB Output is correct
3 Correct 51 ms 2304 KB Output is correct
4 Correct 48 ms 2304 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 24 ms 2304 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 59 ms 2304 KB Output is correct
11 Correct 53 ms 2304 KB Output is correct
12 Incorrect 48 ms 2304 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3448 KB Output is correct
2 Correct 122 ms 3448 KB Output is correct
3 Correct 137 ms 3576 KB Output is correct
4 Correct 50 ms 2304 KB Output is correct
5 Correct 40 ms 2304 KB Output is correct
6 Correct 31 ms 2176 KB Output is correct
7 Correct 14 ms 2304 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 72 ms 3340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2304 KB Output is correct
2 Correct 27 ms 2304 KB Output is correct
3 Correct 89 ms 3320 KB Output is correct
4 Correct 24 ms 2304 KB Output is correct
5 Correct 98 ms 3448 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Incorrect 74 ms 3448 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2304 KB Output is correct
2 Correct 19 ms 2304 KB Output is correct
3 Correct 51 ms 2304 KB Output is correct
4 Correct 48 ms 2304 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 24 ms 2304 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 59 ms 2304 KB Output is correct
11 Correct 53 ms 2304 KB Output is correct
12 Incorrect 48 ms 2304 KB Output isn't correct
13 Halted 0 ms 0 KB -