oj.uz

Submission #544964

# Submission time Handle Problem Language Result Execution time Memory
544964 2022-04-03T08:38:01 Z inluminas Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 21 ms 4044 KB 
#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=202;
vector<pair<ll,ll>>adj[lmt][2];
ll dis[lmt][2][2];

int main(){
	fastio;

	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		ll u,v,c,d;
		cin>>u>>v>>c>>d;
		adj[u][0].push_back({c,v});
		adj[v][1].push_back({c+d,u});
	}

	for(int i=0;i<=n;i++){
		for(int j=0;j<2;j++) for(int k=0;k<2;k++) dis[i][j][k]=inf;
	}

	set<array<ll,4>>q;
	q.insert({0,1,0,0});

	while(!q.empty()){
		auto it=q.begin();
		ll val=(*it)[0],u=(*it)[1],ver=(*it)[2],ver2=(*it)[3];

		q.erase(it);

		if(dis[u][ver][ver2]<val) continue;

		for(auto [w,v]:adj[u][0]){
			if(v==n){
				if(dis[v][ver][1]>val+w){
					q.erase({dis[v][ver][1],v,ver,1});
					dis[v][ver][1]=val+w;
					q.insert({dis[v][ver][1],v,ver,1});
				}
			}else{
				if(dis[v][ver][ver2]>val+w){
					q.erase({dis[v][ver][ver2],v,ver,ver2});
					dis[v][ver][ver2]=val+w;
					q.insert({dis[v][ver][ver2],v,ver,ver2});
				}
			}
		}

		if(ver) continue;

		for(auto [w,v]:adj[u][1]){
			if(v==n){
				if(dis[v][1][1]>val+w){
					q.erase({dis[v][1][1],v,1,1});
					dis[v][1][1]=val+w;
					q.insert({dis[v][ver][1],v,1,1});
				}
			}else{
				if(dis[v][1][ver2]>val+w){
					q.erase({dis[v][1][ver2],v,1,ver2});
					dis[v][1][ver2]=val+w;
					q.insert({dis[v][1][ver2],v,1,ver2});
				}
			}
		}
	}

	ll ans=min(dis[1][0][1],dis[1][1][1]);
	if(ans==inf) ans=-1;

	cout<<ans<<endl;
	return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:40:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for(auto [w,v]:adj[u][0]){
      |            ^
ho_t4.cpp:58:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |   for(auto [w,v]:adj[u][1]){
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3912 KB Output is correct
2 Correct 19 ms 3920 KB Output is correct
3 Correct 20 ms 4044 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 16 ms 2804 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 3800 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -