제출 #1139445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139445		Math4Life2020	Escape Route (JOI21_escape_route)	C++20	70 / 100	9116 ms	1059880 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 90; const ll INF = 1e18;
pii adj[Nm][Nm]; //{travel time, latest leaving time}
vector<pii> dp[Nm][Nm]; //{latest leaving time, travel time}
ll dp3[Nm][Nm]; //time if leaving at start of day

ll rup(ll x, ll S) {
	ll y = x/S;
	if (x>(y*S)) {
		return (y+1)*S;
	} else {
		return x;
	}
}

struct hashPii {
	size_t operator()(const pii &p) const { return p.first ^ (p.second>>15) ^ (p.second<<15); }
};

vector<pii> prc(vector<pii> vp0) {
	unordered_set<pii,hashPii> s0;
	for (pii p0: vp0) {
		s0.insert(p0);
	}
	vector<pii> v1;
	for (pii p1: s0) {
		v1.push_back(p1);
	}
	return v1;
}

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) {
	for (ll i=0;i<Nm;i++) {
		for (ll j=0;j<Nm;j++) {
			adj[i][j]={INF,-INF};
		}
	}
	vector<pair<ll,pii>> vxy;
	for (ll m=0;m<M;m++) {
		adj[A[m]][B[m]]={L[m],C[m]-L[m]};
		adj[B[m]][A[m]]=adj[A[m]][B[m]];
		vxy.push_back({C[m]-L[m],{A[m],B[m]}});
		vxy.push_back({C[m]-L[m],{B[m],A[m]}});
	}
	sort(vxy.begin(),vxy.end());
	for (auto pxy: vxy) {
		ll x = pxy.second.first;
		ll y = pxy.second.second;
		vector<ll> dp2(N,INF);
		vector<bool> pr2(N,false); //is processed
		dp2[y]=adj[x][y].first+adj[x][y].second;
		while (1) {
			ll zc = -1; ll tc = INF;
			for (ll z=0;z<N;z++) {
				if (!pr2[z] && dp2[z]<tc) {
					zc = z; tc = dp2[z];
				}
			}
			if (zc == -1) {
				break;
			}
			pr2[zc]=1;
			for (ll z1=0;z1<N;z1++) {
				if (tc<=adj[zc][z1].second) {
					dp2[z1] = min(dp2[z1],tc+adj[zc][z1].first);
				}
			}
		}
		vector<ll> dp1(N,-INF);
		vector<bool> pr1(N,false);
		dp1[x]=adj[x][y].second;
		while (1) {
			ll zc = -1; ll tc = -INF;
			for (ll z=0;z<N;z++) {
				if (!pr1[z] && dp1[z]>tc) {
					zc = z; tc = dp1[z];
				}
			}
			if (zc==-1) {
				break;
			}
			pr1[zc]=1;
			for (ll z1=0;z1<N;z1++) {
				if (tc<=(adj[z1][zc].first+adj[z1][zc].second) && (tc-adj[zc][z1].first)>=0LL) {
					dp1[z1] = max(dp1[z1],tc-adj[zc][z1].first); 
				}
			}
		}
		for (ll a=0;a<N;a++) {
			for (ll b=0;b<N;b++) {
				if (a!=b && dp1[a]!=-INF && dp2[b]!=INF) {
					dp[a][b].push_back({dp1[a],dp2[b]-dp1[a]});
				}
			}
		}
	}
	for (ll x=0;x<N;x++) {
		for (ll y=0;y<N;y++) {
			dp3[x][y]=INF;
			if (x==y || dp[x][y].size()==0) {
				continue;
			}
			//dp: {latest leaving time, travel time}
			//dptw: {travel time, latest leaving time}
			vector<pii> dptw;
			for (pii p0: dp[x][y]) {
				dptw.push_back({p0.second,p0.first});
			}
			dptw = prc(dptw);
			sort(dptw.begin(),dptw.end());
			dp[x][y].clear();
			ll llt0 = -INF;
			for (pii p0: dptw) {
				if (p0.second>llt0) {
					llt0 = p0.second;
					dp[x][y].push_back({p0.second,p0.first});
				}
			}
			dp3[x][y]=dptw[0].first;
		}
	}
	for (ll k=0;k<N;k++) {
		for (ll i=0;i<N;i++) {
			for (ll j=0;j<N;j++) {
				if (i==j) {
					continue;
				}
				dp3[i][j]=min(dp3[i][j],rup(dp3[i][k],S)+dp3[k][j]);
			}
		}
	}
	vector<ll> ansv; //ans vector
	for (ll q=0;q<Q;q++) {
		ll ans = INF;
		ll x = U[q]; ll y = V[q]; ll t0 = T[q];
		auto A0 = lower_bound(dp[x][y].begin(),dp[x][y].end(),(pii){t0,-INF});
		if (A0 != dp[x][y].end()) {
			ans = (*A0).second;
		}
		for (ll z=0;z<N;z++) {
			if (dp[x][z].size()>0 && dp[x][z].back().first>=t0) {
				ans = min(ans,S-t0+dp3[z][y]);
			}
		}
		ans = min(ans,S-t0+dp3[x][y]);
		ansv.push_back(ans);
	}
	return ansv;
	//exit(0);
}

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