Submission #1182588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182588		8pete8	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	765 ms	5140 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int32_t,int32_t>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5,inf=1e18,minf=-1e18,lg=30,Mxn=1e9;
//#undef int
int n,k,m,d,q;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

vector<pii>adj[202];

vector<pair<int,pii>>e;

int cost[mxn+10];
int dist[202][202][2][2];
//without, at, start from
vector<int>E[202][202];
void dijk(int ban,int x,int y,int z){
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=1;i<=n;i++)dist[ban][i][y][z]=inf;
	if(ban==x)return;
	dist[ban][x][y][z]=0;
	pq.push({0,x});
	while(!pq.empty()){
		int cur=pq.top().s,C=pq.top().f;
		pq.pop();
		if(dist[ban][cur][y][z]!=C)continue;
		for(auto i:adj[cur])if(i.f!=ban&&(ll)(dist[ban][i.f][y][z])>(ll)(dist[ban][cur][y][z]+i.s)){
			dist[ban][i.f][y][z]=dist[ban][cur][y][z]+i.s;
			pq.push({dist[ban][i.f][y][z],i.f});
		}
	}
}

int get(int x,int y,int a,int b,int c){
	//get dist with edge a,b,c inverted from x->y
	//not use inverted b->a
	ll ans=min(dist[a][y][(x==n)][0],dist[b][y][(x==n)][0]);
	if(E[b][a].size()){
		int k=(E[b][a][0]==c);
		if(E[b][a].size()>k){
			ans=min(ans,(ll)(dist[a][b][(x==n)][0]+dist[b][a][(y==n)][1]+E[b][a][k]));
		}
	}
	//use
	ans=min(ans,(ll)(dist[b][a][(x==n)][0]+dist[a][b][(y==n)][1]+c));
	return ans;
}
int32_t main(){
	fastio
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c>>cost[i];
		E[a][b].pb(c);
		e.pb({c,{a,b}});
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		sort(all(E[i][j]));
		if(E[i][j].size())adj[i].pb({j,E[i][j][0]});
	}
	
	//2n((n+m)log(n))=2(10^7)log(200)=1.6x10^8
	//we can kinda opt the size of m to (n^2) to make it
	//=2(8x10^6)log(200)=(1.6x10^7)log(200)=1.28 x 10^8
	for(int i=1;i<=n;i++)dijk(i,1,0,0),dijk(i,n,1,0);
	
	for(int i=1;i<=n;i++)adj[i].clear();

	

	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(E[i][j].size())adj[j].pb({i,E[i][j][0]});
	
	for(int i=1;i<=n;i++)dijk(i,1,0,1),dijk(i,n,1,1);
	int x=inf,y=inf;
	ll ans=inf;
	for(auto i:adj[n])x=min(x,i.s+dist[n][i.f][0][0]);
	for(auto i:adj[1])y=min(y,i.s+dist[1][i.f][1][0]);
	ans=min(ans,(ll)(x+y));
	
	int c=0;
	for(auto i:e){
		ans=min(ans,(ll)(cost[c]+get(1,n,i.s.s,i.s.f,i.f)+get(n,1,i.s.s,i.s.f,i.f)));
		c++;
	}
	if(ans==inf)cout<<-1<<'\n';
	else cout<<ans<<'\n';
}

Compilation message (stderr)

ho_t4.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
ho_t4.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | void setIO(string name){
      |                       ^
ho_t4.cpp:37:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   37 | void dijk(int ban,int x,int y,int z){
      |                                    ^
ho_t4.cpp:54:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 | int get(int x,int y,int a,int b,int c){
      |                                      ^
ho_t4.cpp:68:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | int32_t main(){
      |              ^
ho_t4.cpp: In function 'void setIO(std::string)':
ho_t4.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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