oj.uz

Submission #202312

# Submission time Handle Problem Language Result Execution time Memory
202312 2020-02-15T09:36:32 Z amoo_safar Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 2680 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const int N = 2e2 + 10;
const int M = 2e5 + 10;
const ll Inf = 1e15;

ll n, m;
ll u[M], v[M], c[M], d[M], ans[M];
ll G[N][N], W[N][N], mk[N], dis[N];

void Build(){
	memset(G, 31, sizeof G);
	memset(mk, 0, sizeof mk);
	memset(dis, 31, sizeof dis);
	memset(W, -1, sizeof W);
	for(int i = 0; i < m; i++){
		G[u[i]][v[i]] = min(G[u[i]][v[i]], c[i]);
		if(G[u[i]][v[i]] == c[i]) W[u[i]][v[i]] = i;
	}
}

ll Solve(int idx){
	swap(u[idx], v[idx]);
	Build();
	dis[1] = 0;
	for(int i = 0; i < n; i++){
		ll mn = Inf, id = -1;
		for(int j = 1; j <= n; j++)
			if(!mk[j] && dis[j] < mn){
				mn = dis[j];
				id = j;
			}
		if(id == -1) break;
		mk[id] = 1;
		for(int j = 1; j <= n; j++)
			if(dis[j] > dis[id] + G[id][j]){
				dis[j] = dis[id] + G[id][j];
			}
	}
	swap(u[idx], v[idx]);
	return dis[n];
}

void Main(){
	for(int i = 0; i < m; i++){
		ans[i] += Solve(i);
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i++) cin >> u[i] >> v[i] >> c[i] >> d[i];
	ll Ans = Solve(m);
	Main();
	for(int i = 0; i < m; i++){
		if(u[i] == 1 || u[i] == n) u[i] = n + 1 - u[i];
		if(v[i] == 1 || v[i] == n) v[i] = n + 1 - v[i];
	}
	Ans += Solve(m);
	Main();
	for(int i = 0; i < m; i++) Ans = min(Ans, d[i] + ans[i]);
	cout << (Ans < Inf ? Ans : -1) << '\n';
	return 0;
}
/*
4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1276 KB Output is correct
2 Correct 17 ms 1016 KB Output is correct
3 Correct 370 ms 1144 KB Output is correct
4 Correct 374 ms 1400 KB Output is correct
5 Correct 65 ms 1144 KB Output is correct
6 Correct 19 ms 1016 KB Output is correct
7 Correct 6 ms 1016 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 52 ms 1144 KB Output is correct
10 Correct 375 ms 1144 KB Output is correct
11 Correct 370 ms 1144 KB Output is correct
12 Correct 361 ms 1144 KB Output is correct
13 Correct 250 ms 1272 KB Output is correct
14 Correct 283 ms 1144 KB Output is correct
15 Correct 281 ms 1144 KB Output is correct
16 Correct 276 ms 1144 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 1148 KB Output is correct
2 Correct 33 ms 1016 KB Output is correct
3 Execution timed out 1084 ms 2460 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 1276 KB Output is correct
2 Correct 17 ms 1016 KB Output is correct
3 Correct 370 ms 1144 KB Output is correct
4 Correct 374 ms 1400 KB Output is correct
5 Correct 65 ms 1144 KB Output is correct
6 Correct 19 ms 1016 KB Output is correct
7 Correct 6 ms 1016 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 52 ms 1144 KB Output is correct
10 Correct 375 ms 1144 KB Output is correct
11 Correct 370 ms 1144 KB Output is correct
12 Correct 361 ms 1144 KB Output is correct
13 Correct 250 ms 1272 KB Output is correct
14 Correct 283 ms 1144 KB Output is correct
15 Correct 281 ms 1144 KB Output is correct
16 Correct 276 ms 1144 KB Output is correct
17 Execution timed out 1095 ms 2680 KB Time limit exceeded
18 Halted 0 ms 0 KB -