Submission #210877

#	Time	Username	Problem	Language	Result	Execution time	Memory
210877		username	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1090 ms	4216 KiB

ho_t4

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define tr(it,a) for(auto it:a)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define umin(x,y) (x=min(x,(y)))
#define umax(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
//
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
 #define __db
#ifdef __db
	#define IOS
	#define prt(...) cerr<<__VA_ARGS__
	#define ary(s,t) for(auto it=(s);it!=(t);++it)prt(*it<<" ");prt(endl);
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define prt(...)
	#define ary(...)
#endif
//
struct ed{
	int u,v,c,d;
};

const int maxn=209,maxm=5e4+9,inf=1ll<<60;
int n,m,res=inf,pre[maxn],dis[2][2][maxn];
bitset<maxn>ok,used;
vector<int>g[maxn],rg[maxn];
ed eds[maxm];

int dijk(vector<int>*gg,int*dd,int s,int t,int rev){
	fill(dd,dd+n,inf);
	ok.reset();
	dd[s]=0;
	REP(k,0,n){
		int u=-1;
		REP(i,0,n){
			if(!ok[i]&&(u<0||dd[i]<dd[u])){
				u=i;
			}
		}
		ok[u]=1;
		if(rev>=0&&(u==eds[rev].u||u==eds[rev].v)){
			int ex=0;
			REP(i,0,gg[u].size())ex|=gg[u][i]==rev;
			if(!ex){
				int v=u^eds[rev].u^eds[rev].v;
				if(dd[v]>dd[u]+eds[rev].c){
					dd[v]=dd[u]+eds[rev].c;
					pre[v]=rev;
				}
			}
		}
		REP(i,0,gg[u].size()){
			int e=gg[u][i],v=u^eds[e].u^eds[e].v;
			if(e!=rev&&dd[v]>dd[u]+eds[e].c){
				dd[v]=dd[u]+eds[e].c;
				pre[v]=e;
			}
		}
	}
	return dd[t];
}

main(){
	IOS;
	cin>>n>>m;
	REP(i,0,m){
		int u,v,c,d;cin>>u>>v>>c>>d,--u,--v;
		eds[i]=ed{u,v,c,d};
		g[u].pb(i);
		rg[v].pb(i);
	}
	dijk(g,dis[0][0],0,n-1,-1);
	REP(i,1,n)used[pre[i]]=1;
	dijk(g,dis[0][1],n-1,0,-1);
	REP(i,0,n-1)used[pre[i]]=1;
	dijk(rg,dis[1][0],0,n-1,-1);
	dijk(rg,dis[1][1],n-1,0,-1);
	REP(i,0,m){
		if(!used[i]){
			int x=min(dis[0][0][n-1],dis[0][0][eds[i].v]+eds[i].c+dis[1][1][eds[i].u]);
			int y=min(dis[0][1][0],dis[0][1][eds[i].v]+eds[i].c+dis[1][0][eds[i].u]);
			umin(res,eds[i].d+x+y);
		}
	}
	REP(i,0,m){
		if(used[i]){
			umin(res,eds[i].c+dijk(g,dis[0][0],0,n-1,i)+dijk(g,dis[0][0],n-1,0,i));
		}
	}
	cout<<res<<endl;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int_fast64_t dijk(std::vector<long int>*, int_fast64_t*, int_fast64_t, int_fast64_t, int_fast64_t)':
ho_t4.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
ho_t4.cpp:63:4: note: in expansion of macro 'REP'
    REP(i,0,gg[u].size())ex|=gg[u][i]==rev;
    ^~~
ho_t4.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
ho_t4.cpp:72:3: note: in expansion of macro 'REP'
   REP(i,0,gg[u].size()){
   ^~~
ho_t4.cpp: At global scope:
ho_t4.cpp:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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