Submission #943128

#	Time	Username	Problem	Language	Result	Execution time	Memory
943128		MilosMilutinovic	Escape Route (JOI21_escape_route)	C++17	0 / 100	9069 ms	153304 KiB

escape_route

#include "escape_route.h"
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const ll inf=(ll)1e18;
int n,tot;
int v[100005],nxt[100005],h[95];
ll s,c[100005],b[100005],res[3000005];
vector<pair<ll,int>> qs[95][95];
pair<ll,ll> d[95];

void addedge(int x,int y,ll w,ll t){
	v[++tot]=y; c[tot]=w; b[tot]=t; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; c[tot]=w; b[tot]=t; nxt[tot]=h[y]; h[y]=tot;
}

pair<ll,ll> dijkstra(int u,int v,ll t){
	for(int i=0;i<n;i++) d[i]=mp(inf,0ll);
	d[u]=mp(0,t);
	set<pair<pair<ll,ll>,int>> st;
	st.emplace(mp(d[u],u));
	while(!st.empty()){
		auto it=st.begin();
		int x=it->se;
		st.erase(it);
		for(int p=h[x];p;p=nxt[p]){
			pair<ll,ll> nd;
			if(d[x].se+c[p]<=b[p]){
				nd.fi=d[x].fi;
				nd.se=d[x].se+c[p];
			}else{
				nd.fi=d[x].fi+1;
				nd.se=c[p];
			}
			if(nd<d[::v[p]]){
				if(d[::v[p]].fi!=inf) st.erase(st.find(mp(d[::v[p]],::v[p])));
				d[::v[p]]=nd;
				st.insert(mp(d[::v[p]],::v[p]));
			}
		}
	}
	return d[v];
}

vector<ll> calculate_necessary_time(
	int N,int M,ll S,int Q,vector<int> A,vector<int> B,
	vector<ll> L,vector<ll> C,vector<int> U,
	vector<int> V,vector<ll> T){
	n=N; s=S;
	for(int i=0;i<M;i++) addedge(A[i],B[i],L[i],C[i]);
	for(int i=0;i<Q;i++){
		qs[U[i]][V[i]].pb(mp(T[i],i));
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			sort(qs[i][j].begin(),qs[i][j].end());
			int sz=(int)qs[i][j].size();
			for(int k=0;k<sz;k++){
				int l=k+1,r=sz-1,p=k;
				pair<ll,ll> tm=dijkstra(i,j,qs[i][j][k].fi);
				while(l<=r){
					int mid=(l+r)/2;
					pair<ll,ll> tmp=dijkstra(i,j,qs[i][j][mid].fi);
					if(tmp.fi==tm.fi&&tmp.se-tm.se==qs[i][j][mid].fi-qs[i][j][k].fi) p=mid,l=mid+1;
					else r=mid-1;
				}
				for(int f=k;f<=p;f++) res[qs[i][j][k].se]=tm.fi*s+tm.se+(qs[i][j][f].fi-qs[i][j][k].fi)-qs[i][j][f].fi;
				k=p;
			}
		}
	}
	vector<ll> ret;
	for(int i=0;i<Q;i++) ret.pb(res[i]);
	return ret;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30