Submission #237094

#	Time	Username	Problem	Language	Result	Execution time	Memory
237094		wwdd	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	700 ms	7140 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> al;
typedef vector<ll> vl;
typedef pair<pl,pl> egg;
const ll INFL = 1e18;
const int MP = 220;
const int MN = 50500;
al g,h;
vector<vl> ha;
vector<egg> eg;
vl fist,rist;
vl fast,rast;
vl pis, ris;
vl so;
bitset<MN> fs,rs;
bitset<MP> fat,rat;
void dja(vl& w, vl& pa, int s) {
	w.assign(g.size(),INFL);
	pa.assign(g.size(),-1);
	priority_queue<pl,vpl,greater<pl> > pq;
	pq.push({0,s});
	w[s] = 0;
	while(!pq.empty()) {
		pl co = pq.top();pq.pop();
		int u = co.second;
		if(co.first > w[u]) {continue;}
		for(int i=0;i<g[u].size();i++) {
			int v = g[u][i].first;
			ll d = g[u][i].second;
			if(d+w[u] < w[v]) {
				w[v] = d+w[u];
				int e = ha[u][i];
				pa[v] = e;
				pq.push({w[v],v});
			}
		}
	}
}
void djb(vl& w, al& gr, int s) {
	w.assign(gr.size(),INFL);
	priority_queue<pl,vpl,greater<pl> > pq;
	pq.push({0,s});
	w[s] = 0;
	while(!pq.empty()) {
		pl co = pq.top();pq.pop();
		int u = co.second;
		if(co.first > w[u]) {continue;}
		for(int i=0;i<gr[u].size();i++) {
			int v = gr[u][i].first;
			ll d = gr[u][i].second;
			if(d+w[u] < w[v]) {
				w[v] = d+w[u];
				pq.push({w[v],v});
			}
		}
	}
}
void pre() {
	dja(fist,pis, 0);
	dja(rist,ris, g.size()-1);
	djb(fast,h,g.size()-1);
	djb(rast,h,0);
	int pp = g.size()-1;
	while(pis[pp] != -1) {
		fat.set(pp);
		fs.set(pis[pp]);
		pp = eg[pis[pp]].first.first;
	}
	fat.set(0);
	for(int i=0;i<ris.size();i++) {
		if(ris[i] != -1) {
			rs.set(ris[i]);
		}
	}
	pp = 0;
	while(ris[pp] != -1) {
		rat.set(pp);
		rs.set(ris[pp]);
		pp = eg[ris[pp]].first.first;
	}
	rat.set(g.size()-1);
}
ll proc(int e) {
	vl tp;
	int u = eg[e].first.first;
	int v = eg[e].first.second;
	ll ex = eg[e].second.second;
	ll reg = eg[e].second.first;
	int eid = so[e];
	ll fdi,rdi;
	if(fs[e]) {
		g[u][eid].second = INFL;
		g[v].push_back({u,reg});
		djb(tp,g,0);
		fdi = tp[g.size()-1];
		g[v].pop_back();
		g[u][eid].second = reg;
	} else {
		fdi = fist[g.size()-1];
		fdi = min(fdi,fist[v]+fast[u]+reg);
	}
	if(rs[e]) {
		g[u][eid].second = INFL;
		g[v].push_back({u,reg});
		djb(tp,g,g.size()-1);
		rdi = tp[0];
		g[v].pop_back();
		g[u][eid].second = reg;
	} else {
		rdi = rist[0];
		rdi = min(rdi,rist[v]+rast[u]+reg);
	}
	return fdi+rdi+ex;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n,m;
	cin >> n >> m;
	g.assign(n,vpl());
	h.assign(n,vpl());
	ha.assign(n,vl());
	fist.assign(n,INFL);
	rist.assign(n,INFL);
	for(int i=0;i<m;i++) {
		ll a,b,c,d;
		cin >> a >> b >> c >> d;
		a--;b--;
		so.push_back(g[a].size());
		g[a].push_back({b,c});
		h[b].push_back({a,c});
		ha[a].push_back(i);
		eg.push_back({{a,b},{c,d}});
	}

	pre();
	ll res = fist[n-1]+rist[0];
	for(int i=0;i<m;i++) {
		res = min(res,proc(i));
	}
	if(res >= INFL) {
		cout << -1 << '\n';
	} else {
		cout << res << '\n';
	}
}

Compilation message (stderr)

ho_t4.cpp: In function 'void dja(vl&, vl&, int)':
ho_t4.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) {
               ~^~~~~~~~~~~~
ho_t4.cpp: In function 'void djb(vl&, al&, int)':
ho_t4.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gr[u].size();i++) {
               ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void pre()':
ho_t4.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ris.size();i++) {
              ~^~~~~~~~~~~

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