oj.uz

Submission #537159

# Submission time Handle Problem Language Result Execution time Memory
537159 2022-03-14T16:50:55 Z alvingogo Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 4192 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
 
const int inf=4e18;
struct eg{
	int v,id,c,d;
};
vector<vector<eg> > e;
vector<int> p[2];
vector<int> dz[2];
int n;
int dijk(int x,int y,int t){
	p_q<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	vector<int> dis(n,inf);
	dis[x]=0;
	pq.push({0,x});
	while(!pq.empty()){
		auto h=pq.top();
		pq.pop();
		if(dis[h.sc]!=h.fs){
			continue;
		}
		for(auto a:e[h.sc]){
			if(dis[a.v]>dis[h.sc]+a.c){
				dis[a.v]=dis[h.sc]+a.c;
				if(t<2){
					p[t][a.v]=a.id;
				}
				pq.push({dis[a.v],a.v});
			}
		}
	}
	if(t<2){
		dz[t]=dis;
	}
	assert(dis[y]<=inf);
	return dis[y];
}
pair<vector<int>,vector<int> > fw(vector<vector<int> >& ez){
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				ez[i][j]=min(ez[i][j],ez[i][k]+ez[k][j]);
			}
		}
	}
	vector<int> d1(n),d2(n);
	for(int i=0;i<n;i++){
		d1[i]=ez[i][n-1];
		d2[i]=ez[i][0];
	}
	return {d1,d2};
}
signed main(){
	AquA;
	int m;
	cin >> n >> m;
	e.resize(n);
	p[0].resize(n,-1);
	p[1].resize(n,-1);
	vector<vector<int> > ez(n,vector<int>(n,inf));
	for(int i=0;i<m;i++){
		int u,v,c,d;
		cin >> u >> v >> c >> d;
		u--;
		v--;
		e[u].push_back({v,i+1,c,d});
		ez[u][v]=min(ez[u][v],c);
	}
	for(int i=0;i<n;i++){
		ez[i][i]=0;
	}
	vector<int> to[2];
	//to[0].resize(n);
	//to[1].resize(n);
	auto tmp=fw(ez);
	to[0]=tmp.fs;
	to[1]=tmp.sc;
	int ans=inf;
	ans=min(inf,dijk(0,n-1,0)+dijk(n-1,0,1));
	for(int i=0;i<n;i++){
		for(int j=0;j<e[i].size();j++){
			auto h=e[i][j];
			e[h.v].push_back({i,-1,h.c+h.d,-1});
			e[i][j].c+=2*inf;
			ans=min(ans,dijk(0,n-1,2)+dijk(n-1,0,2));
			e[i][j].c-=2*inf;
			auto y=e[h.v].back();
			assert(y.v==i && y.id==-1 && y.c==h.c+h.d && y.d==-1);
			e[h.v].pop_back();
		}
	}
	if(ans>=inf){
		cout << -1 << "\n";
	}
	else{
		cout << ans << "\n";
	}
	
	return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:88:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<eg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int j=0;j<e[i].size();j++){
      |               ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 724 KB Output is correct
2 Correct 11 ms 668 KB Output is correct
3 Correct 49 ms 844 KB Output is correct
4 Correct 55 ms 724 KB Output is correct
5 Correct 12 ms 340 KB Output is correct
6 Correct 7 ms 668 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 74 ms 728 KB Output is correct
11 Correct 72 ms 724 KB Output is correct
12 Correct 78 ms 724 KB Output is correct
13 Incorrect 27 ms 740 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 724 KB Output is correct
2 Correct 12 ms 596 KB Output is correct
3 Execution timed out 1086 ms 3156 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 724 KB Output is correct
2 Correct 11 ms 668 KB Output is correct
3 Correct 49 ms 844 KB Output is correct
4 Correct 55 ms 724 KB Output is correct
5 Correct 12 ms 340 KB Output is correct
6 Correct 7 ms 668 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 74 ms 728 KB Output is correct
11 Correct 72 ms 724 KB Output is correct
12 Correct 78 ms 724 KB Output is correct
13 Incorrect 27 ms 740 KB Output isn't correct
14 Halted 0 ms 0 KB -