oj.uz

Submission #861067

# Submission time Handle Problem Language Result Execution time Memory
861067 2023-10-15T08:43:19 Z phoenix0423 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 21716 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 4e5 + 5;
const ll INF = 2e9 + 7;
struct edge{
	int a, b, c, d;
	edge(){}
	edge(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d){}
};
int n, m;
vector<int> adj[maxn], radj[maxn];
vector<edge> e;
int invalid[10000];

int main(void){
	fastio;
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a, b, c, d;
		cin>>a>>b>>c>>d;
		a--, b--;
		adj[a].pb(i);
		radj[b].pb(i);
		e.pb(edge(a, b, c, d));
	}
	vector<ll> dist(n, INF), dist2(n, INF), rdist(n, INF), rdist2(n, INF);
	dist[0] = 0, dist2[n - 1] = 0, rdist[n - 1] = 0, rdist2[0] = 0;
	auto dijkstra = [&](vector<ll>& dist) -> void{
		vector<int> vis(n);
		for(int i = 0; i < n; i++){
			ll mn = INF, id = 0;
			for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
			vis[id] = 1;
			for(auto x : adj[id]){
				if(invalid[x]) continue;
				auto [a, b, c, d] = e[x];
				dist[b] = min(dist[b], dist[a] + c);
			}
		}
	};
	auto rdijkstra = [&](vector<ll>& dist) -> void{
		vector<int> vis(n);
		for(int i = 0; i < n; i++){
			ll mn = INF, id = 0;
			for(int j = 0; j < n; j++) if(!vis[j] && dist[j] < mn) mn = dist[j], id = j;
			vis[id] = 1;
			for(auto x : radj[id]){
				auto [a, b, c, d] = e[x];
				dist[a] = min(dist[a], dist[b] + c);
			}
		}
	};
	dijkstra(dist);
	dijkstra(dist2);
	rdijkstra(rdist);
	rdijkstra(rdist2);
	ll ans = dist[n - 1] + dist2[0];
	for(int i = 0; i < m; i++){
		auto [a, b, c, d] = e[i];
		if(dist[a] + rdist[b] + c == dist[n - 1] || dist2[a] + rdist2[b] + c == dist2[0]){
			invalid[i] = 1;
			e.pb(edge(b, a, c, d));
			adj[b].pb(m);
			vector<ll> ndist(n, INF), ndist2(n, INF);
			ndist[0] = 0, ndist2[n - 1] = 0;
			dijkstra(ndist), dijkstra(ndist2);
			ans = min(ans, ndist[n - 1] + ndist2[0] + d);
			e.pop_back();
			adj[b].pop_back();
			invalid[i] = 0;
			continue;
		}
		//invert : becomes b->a
		ans = min(ans, dist[n - 1] + dist2[b] + rdist2[a] + c + d);
		ans = min(ans, dist2[0] + dist[b] + rdist[a] + c + d);
	}
	cout<<(ans < INF ? ans : -1)<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 19540 KB Output is correct
2 Correct 13 ms 19036 KB Output is correct
3 Correct 7 ms 19292 KB Output is correct
4 Correct 7 ms 19328 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19032 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 42 ms 19128 KB Output is correct
11 Correct 55 ms 19292 KB Output is correct
12 Correct 52 ms 19288 KB Output is correct
13 Incorrect 5 ms 19288 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 21712 KB Output is correct
2 Correct 29 ms 21464 KB Output is correct
3 Correct 26 ms 21716 KB Output is correct
4 Correct 7 ms 19288 KB Output is correct
5 Correct 10 ms 19288 KB Output is correct
6 Correct 6 ms 19292 KB Output is correct
7 Correct 6 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Incorrect 19 ms 21632 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 19292 KB Output is correct
2 Correct 19 ms 19036 KB Output is correct
3 Execution timed out 1020 ms 21712 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 19540 KB Output is correct
2 Correct 13 ms 19036 KB Output is correct
3 Correct 7 ms 19292 KB Output is correct
4 Correct 7 ms 19328 KB Output is correct
5 Correct 6 ms 19292 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19032 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19292 KB Output is correct
10 Correct 42 ms 19128 KB Output is correct
11 Correct 55 ms 19292 KB Output is correct
12 Correct 52 ms 19288 KB Output is correct
13 Incorrect 5 ms 19288 KB Output isn't correct
14 Halted 0 ms 0 KB -