Submission #1191502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191502		8pete8	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	778 ms	31676 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});
		}
	}
}
vector<pii>adj2[mxn+10];
vector<int>pref[mxn+10][2],suf[mxn+10][2];

int get(int x,int y,int a,int b,int c,int id){
	//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(adj2[a].size()>1){
		int g=inf;
		if(id)g=min(g,pref[a][x==n][id-1]);
		if(id+1<adj2[a].size())g=min(g,suf[a][x==n][id+1]);
		ans=min(ans,dist[b][a][y==n][1]+g);
	}
	//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];
		adj2[b].pb({a,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));
	for(int i=1;i<=n;i++){
		for(auto j:adj2[i]){
			for(int k=0;k<2;k++){
				pref[i][k].pb(dist[i][j.f][k][0]+e[j.s].f);
				suf[i][k].pb(dist[i][j.f][k][0]+e[j.s].f);
			}
		}
		for(int k=0;k<2;k++){
			for(int j=1;j<adj2[i].size();j++)pref[i][k][j]=min(pref[i][k][j-1],pref[i][k][j]);
			for(int j=adj2[i].size()-2;j>=0;j--)suf[i][k][j]=min(suf[i][k][j+1],suf[i][k][j]);
		}
		int bruh=0;
		for(auto j:adj2[i]){
			ans=min(ans,cost[j.s]+get(1,n,i,j.f,e[j.s].f,bruh)+get(n,1,i,j.f,e[j.s].f,bruh));
			bruh++;
		}
		
	}
	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:36:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   36 | void dijk(int ban,int x,int y,int z){
      |                                    ^
ho_t4.cpp:55:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 | int get(int x,int y,int a,int b,int c,int id){
      |                                             ^
ho_t4.cpp:70:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   70 | 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