Submission #525067

#	Time	Username	Problem	Language	Result	Execution time	Memory
525067		mosiashvililuka	Olympic Bus (JOI20_ho_t4)	C++14	37 / 100	1089 ms	8096 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
const int N=1500000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,C,D,A[50009],B[50009],dis[209][209],bo[50009],dis2[209][209],pas,z[209],zi,BO[50009],DIS[209][209],Adis[209][209];
pair <pair <int, int>, pair <int, int> > p[50009];
pair <int, int> P;
multiset <pair <pair <int, int>, int> > v[209],V[209];
multiset <pair <pair <int, int>, int> >::iterator it;
multiset <pair <int, int> > s;
multiset <pair <int, int> >::iterator tt;
void DJI(int q){
	int h,qw,we,er;
	for(h=1; h<=a; h++){
		dis[q][h]=N;bo[h]=0;
	}
	s.clear();
	s.insert({0,q});dis[q][q]=0;
	while(s.size()){
		while(s.size()){
			tt=s.end();tt--;
			P=(*tt);
			if(bo[P.second]==0) break;
			s.erase(tt);
		}
		if(s.size()==0) break;
		qw=-P.first;we=P.second;bo[we]=1;
		tt=s.end();tt--;s.erase(tt);
		for(it=v[we].begin(); it!=v[we].end(); it++){
			if(dis[q][(*it).first.first]>dis[q][we]+(*it).first.second){
				if(dis[q][(*it).first.first]!=N){
					s.erase(s.lower_bound({-dis[q][(*it).first.first],(*it).first.first}));
				}
				dis[q][(*it).first.first]=dis[q][we]+(*it).first.second;
				dis2[q][(*it).first.first]=(*it).second;
				s.insert({-dis[q][(*it).first.first],(*it).first.first});
			}
		}
	}
}
void ADJI(int q){
	int h,qw,we,er;
	for(h=1; h<=a; h++){
		Adis[q][h]=N;bo[h]=0;
	}
	s.clear();
	s.insert({0,q});Adis[q][q]=0;
	while(s.size()){
		while(s.size()){
			tt=s.end();tt--;
			P=(*tt);
			if(bo[P.second]==0) break;
			s.erase(tt);
		}
		if(s.size()==0) break;
		qw=-P.first;we=P.second;bo[we]=1;
		tt=s.end();tt--;s.erase(tt);
		for(it=V[we].begin(); it!=V[we].end(); it++){
			if(Adis[q][(*it).first.first]>Adis[q][we]+(*it).first.second){
				if(Adis[q][(*it).first.first]!=N){
					s.erase(s.lower_bound({-Adis[q][(*it).first.first],(*it).first.first}));
				}
				Adis[q][(*it).first.first]=Adis[q][we]+(*it).first.second;
				s.insert({-Adis[q][(*it).first.first],(*it).first.first});
			}
		}
	}
}
//
void DJI2(int q){
	int h,qw,we,er;
	for(h=1; h<=a; h++){
		DIS[q][h]=N;bo[h]=0;
	}
	s.clear();
	s.insert({0,q});DIS[q][q]=0;
	while(s.size()){
		while(s.size()){
			tt=s.end();tt--;
			P=(*tt);
			if(bo[P.second]==0) break;
			s.erase(tt);
		}
		if(s.size()==0) break;
		qw=-P.first;we=P.second;bo[we]=1;
		tt=s.end();tt--;s.erase(tt);
		for(it=v[we].begin(); it!=v[we].end(); it++){
			if(DIS[q][(*it).first.first]>DIS[q][we]+(*it).first.second){
				if(DIS[q][(*it).first.first]!=N){
					s.erase(s.lower_bound({-DIS[q][(*it).first.first],(*it).first.first}));
				}
				DIS[q][(*it).first.first]=DIS[q][we]+(*it).first.second;
				s.insert({-DIS[q][(*it).first.first],(*it).first.first});
			}
		}
	}
}
//
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=b; i++){
		cin>>c>>d>>C>>D;
		p[i]={{c,d},{C,D}};
		v[c].insert({{d,C},i});
		V[d].insert({{c,C},i});
	}
	DJI(1);
	DJI(a);
	ADJI(1);
	ADJI(a);
	if(dis[1][a]!=N&&dis[a][1]!=N) pas=dis[1][a]+dis[a][1]; else pas=N;
	for(i=1; i<=b; i++){
		BO[i]=0;
	}
	c=a;zi=0;
	while(c!=1&&c!=0){
		zi++;z[zi]=dis2[1][c];
		e=dis2[1][c];
		if(p[e].first.first!=c){
			c=p[e].first.first;
		}else{
			c=p[e].first.second;
		}
	}
	for(i=1; i<=zi; i++) BO[z[i]]=1;
	A[0]=dis[1][a];
	for(i=1; i<=b; i++){
		if(BO[i]==1) continue;
		if(dis[1][p[i].first.second]!=N&&Adis[a][p[i].first.first]!=N) A[i]=dis[1][p[i].first.second]+p[i].second.first+Adis[a][p[i].first.first]; else A[i]=N;
		A[i]=min(A[i],dis[1][a]);
	}
	for(i=1; i<=b; i++){
		if(BO[i]==0) continue;
		it=v[p[i].first.first].lower_bound({{p[i].first.second,p[i].second.first},i});
		v[p[i].first.first].erase(it);
		v[p[i].first.second].insert({{p[i].first.first,p[i].second.first},i});
		DJI2(1);
		A[i]=DIS[1][a];
		it=v[p[i].first.second].lower_bound({{p[i].first.first,p[i].second.first},i});
		v[p[i].first.second].erase(it);
		v[p[i].first.first].insert({{p[i].first.second,p[i].second.first},i});
	}
	//
	//
	for(i=1; i<=b; i++){
		BO[i]=0;
	}
	c=1;zi=0;
	while(c!=a&&c!=0){
		zi++;z[zi]=dis2[a][c];
		e=dis2[a][c];
		if(p[e].first.first!=c){
			c=p[e].first.first;
		}else{
			c=p[e].first.second;
		}
	}
	for(i=1; i<=zi; i++) BO[z[i]]=1;
	B[0]=dis[a][1];
	for(i=1; i<=b; i++){
		if(BO[i]==1) continue;
		if(dis[a][p[i].first.second]!=N&&Adis[1][p[i].first.first]!=N) B[i]=dis[a][p[i].first.second]+p[i].second.first+Adis[1][p[i].first.first]; else B[i]=N;
		B[i]=min(B[i],dis[a][1]);
	}
	for(i=1; i<=b; i++){
		if(BO[i]==0) continue;
		it=v[p[i].first.first].lower_bound({{p[i].first.second,p[i].second.first},i});
		v[p[i].first.first].erase(it);
		v[p[i].first.second].insert({{p[i].first.first,p[i].second.first},i});
		DJI2(a);
		B[i]=DIS[a][1];
		it=v[p[i].first.second].lower_bound({{p[i].first.first,p[i].second.first},i});
		v[p[i].first.second].erase(it);
		v[p[i].first.first].insert({{p[i].first.second,p[i].second.first},i});
	}
	//
	//
	for(i=0; i<=b; i++){
		if(A[i]!=N&&B[i]!=N){
			pas=min(pas,A[i]+B[i]+p[i].second.second);
		}
	}
	if(pas!=N) cout<<pas; else cout<<-1;
	return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'void DJI(int)':
ho_t4.cpp:12:8: warning: variable 'qw' set but not used [-Wunused-but-set-variable]
   12 |  int h,qw,we,er;
      |        ^~
ho_t4.cpp:12:14: warning: unused variable 'er' [-Wunused-variable]
   12 |  int h,qw,we,er;
      |              ^~
ho_t4.cpp: In function 'void ADJI(int)':
ho_t4.cpp:41:8: warning: variable 'qw' set but not used [-Wunused-but-set-variable]
   41 |  int h,qw,we,er;
      |        ^~
ho_t4.cpp:41:14: warning: unused variable 'er' [-Wunused-variable]
   41 |  int h,qw,we,er;
      |              ^~
ho_t4.cpp: In function 'void DJI2(int)':
ho_t4.cpp:70:8: warning: variable 'qw' set but not used [-Wunused-but-set-variable]
   70 |  int h,qw,we,er;
      |        ^~
ho_t4.cpp:70:14: warning: unused variable 'er' [-Wunused-variable]
   70 |  int h,qw,we,er;
      |              ^~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63