oj.uz

Submission #570867

# Submission time Handle Problem Language Result Execution time Memory
570867 2022-05-31T12:58:04 Z inksamurai Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 345028 KB 
#include <bits/stdc++.h>
#include "escape_route.h"
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rng(i,x,n) for(ll i=x;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3wX6R40 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<ll,ll>;
using vi=vector<ll>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

struct E{
	ll to,w,i;
	ll lim;
	E(ll _to,ll _w,ll _i,ll _lim):to(_to),w(_w),i(_i),lim(_lim){}
};

using vll=std::vector<long long>;

std::vector<long long> calculate_necessary_time(
int N,int M, long long S,int Q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T){
	ll n=N,m=M;
	vec(vec(E)) adj(n);
	rep(i,m){
		adj[A[i]].pb(E(B[i],L[i],i,C[i]));
		adj[B[i]].pb(E(A[i],L[i],i,C[i]));
	}
	// starting from node 'v' what is maximum time such that edge 'e' is reachable.
	// O(n^3logn)
	const ll lnf=1e18;
	vec(vec(vll)) edp(n,vec(vll)(n,vll(m,lnf)));
	{
		rep(s,n){
			for(auto &[su,sw,sid,slim]:adj[s]){
				vll dp(n,-1);
				dp[su]=slim-sw;
				priority_queue<pii> pq;
				pq.push({dp[su],su});
				while(sz(pq)){
					auto top=pq.top();
					pq.pop();
					ll cosu=top.fi,v=top.se;
					edp[v][v][sid]=(edp[v][v][sid]==lnf?cosu:max(edp[v][v][sid],cosu));
					if(dp[v]!=cosu) continue;
					for(auto &[u,w,nid,lim]:adj[v]){
						ll ncosu=min(cosu-w,lim-w);
						if(ncosu<0 or dp[u]>=ncosu) continue;
						dp[u]=ncosu;
						pq.push({ncosu,u});
					}
				}
			}
		}
	}
	// print(edp[0][0][2]);
	// starting from node (v,time) evaluate minimum path to reach 'k'
	// O(n^4 * n logn)
	rep(s,n){
		// don't forget pencakes !
		priority_queue<pii,vec(pii),greater<pii>> pq;
		rep(i,m){
			if(edp[s][s][i]==lnf) continue;
			ll max_time=edp[s][s][i];
			pq.push({max_time,s});
			while(sz(pq)){
				auto top=pq.top();
				ll v=top.se;
				ll cosu=top.fi;
				pq.pop();
				if(edp[s][v][i]!=cosu) continue;
				for(auto &[u,w,nid,lim]:adj[v]){
					if(u==s) continue;
					if(cosu+w<=lim){
						if(edp[s][u][i]>cosu+w){
							edp[s][u][i]=cosu+w;
							pq.push({cosu+w,u});
						}
					}
				}
			}
		}
	}
	// evaluate dp(v,u) minimum time to reach 'u' from 'v' 
	// with starting with cost 0
	vec(vll) fdp(n,vll(n,lnf));
	{
		using tpii=pair<ll,pair<ll,ll>>;
		priority_queue<tpii,vec(tpii),greater<tpii>> pq;
		vec(vll) dp;
		rep(s,n){
			pq.push({0,{s,0}});
			dp=vec(vll)(n,vll(n+1,lnf));
			dp[s][0]=0;
			// v,number of days
			while(sz(pq)){
				auto top=pq.top();
				ll now=top.fi,v=top.se.fi,day=top.se.se;
				pq.pop();
				if(dp[v][day]!=now) continue;
				ll x=now%S;
				if(day+1<=n){
					if(dp[v][day+1]>now+(S-x)){
						dp[v][day+1]=now+S-x;
						pq.push({now+S-x,{v,day+1}});
					}
				}
				for(auto &[u,w,id,lim]:adj[v]){
					if(x+w<=lim){
						if(dp[u][day]>now+w){
							dp[u][day]=now+w;
							pq.push({now+w,{u,day}});
						}
					}
				}
			}
			rep(u,n){
				if(s==u) continue;
				ll mi=lnf;
				rep(i,n+1) mi=min(mi,dp[u][i]);
				fdp[s][u]=mi;
			}
		}
	}
	// answer each query from fixed v
	vec(vec(pair<ll,ll>)) qry(n);
	rep(i,Q){
		ll u=U[i],t=T[i];
		qry[u].pb({t,i});
	}
	// print(edp[0][2][1]);
	vll pns(Q);
	rep(v,n){
		sort(qry[v].rbegin(),qry[v].rend());
		vec(pii) rbts;
		rep(i,m){
			if(edp[v][v][i]==lnf) continue;
			// if(v==0) print(edgep[v][v][i]);
			rbts.pb({edp[v][v][i],i});
		}
		sort(rbts.begin(),rbts.end());
		ll r=sz(rbts)-1;
		vll ndp(n,lnf);
		rep(i,sz(qry[v])){
			while(r>=0 and rbts[r].fi>=qry[v][i].fi){
				rep(k,n){
					if(edp[v][k][rbts[r].se]!=lnf){
						ndp[k]=min(ndp[k],edp[v][k][rbts[r].se]-edp[v][v][rbts[r].se]);
					}
				}
				r-=1;
			}
			ll ans=lnf;
			ll u=V[qry[v][i].se];
			rep(k,n){
				// cout<<ndp[k]<<"\n";
				if(ndp[k]!=lnf){
					// if(v==1) print(k,ndp[k],S-qry[v][i].fi+fdp[k][u]);
					ans=min(ans,S-qry[v][i].fi+fdp[k][u]);
				}
			}
			if(ndp[u]!=lnf){
				ans=min(ans,ndp[u]);
			}
			// if(v==0) print(S-qry[v][i].se+fdp[v][u]);
			ans=min(ans,S-qry[v][i].fi+fdp[v][u]);
			pns[qry[v][i].se]=ans;
		}
	}
	return pns;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 41 ms 64980 KB Output is correct
3 Correct 468 ms 64980 KB Output is correct
4 Correct 34 ms 65016 KB Output is correct
5 Correct 49 ms 64948 KB Output is correct
6 Correct 32 ms 65028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1684 ms 127912 KB Output is correct
2 Correct 1757 ms 182404 KB Output is correct
3 Correct 1516 ms 169632 KB Output is correct
4 Correct 1849 ms 192072 KB Output is correct
5 Correct 1802 ms 192012 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 1645 ms 170804 KB Output is correct
8 Correct 1236 ms 195032 KB Output is correct
9 Correct 1641 ms 170820 KB Output is correct
10 Correct 1912 ms 190400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 41 ms 64980 KB Output is correct
3 Correct 468 ms 64980 KB Output is correct
4 Correct 34 ms 65016 KB Output is correct
5 Correct 49 ms 64948 KB Output is correct
6 Correct 32 ms 65028 KB Output is correct
7 Correct 1684 ms 127912 KB Output is correct
8 Correct 1757 ms 182404 KB Output is correct
9 Correct 1516 ms 169632 KB Output is correct
10 Correct 1849 ms 192072 KB Output is correct
11 Correct 1802 ms 192012 KB Output is correct
12 Correct 29 ms 64972 KB Output is correct
13 Correct 1645 ms 170804 KB Output is correct
14 Correct 1236 ms 195032 KB Output is correct
15 Correct 1641 ms 170820 KB Output is correct
16 Correct 1912 ms 190400 KB Output is correct
17 Correct 1686 ms 172056 KB Output is correct
18 Correct 1821 ms 173124 KB Output is correct
19 Correct 1816 ms 183244 KB Output is correct
20 Correct 1597 ms 171848 KB Output is correct
21 Correct 1901 ms 187900 KB Output is correct
22 Correct 2043 ms 189124 KB Output is correct
23 Correct 1819 ms 173408 KB Output is correct
24 Correct 1205 ms 195104 KB Output is correct
25 Correct 1670 ms 172128 KB Output is correct
26 Correct 1870 ms 190764 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 41 ms 64980 KB Output is correct
3 Correct 468 ms 64980 KB Output is correct
4 Correct 34 ms 65016 KB Output is correct
5 Correct 49 ms 64948 KB Output is correct
6 Correct 32 ms 65028 KB Output is correct
7 Correct 1684 ms 127912 KB Output is correct
8 Correct 1757 ms 182404 KB Output is correct
9 Correct 1516 ms 169632 KB Output is correct
10 Correct 1849 ms 192072 KB Output is correct
11 Correct 1802 ms 192012 KB Output is correct
12 Correct 29 ms 64972 KB Output is correct
13 Correct 1645 ms 170804 KB Output is correct
14 Correct 1236 ms 195032 KB Output is correct
15 Correct 1641 ms 170820 KB Output is correct
16 Correct 1912 ms 190400 KB Output is correct
17 Correct 1686 ms 172056 KB Output is correct
18 Correct 1821 ms 173124 KB Output is correct
19 Correct 1816 ms 183244 KB Output is correct
20 Correct 1597 ms 171848 KB Output is correct
21 Correct 1901 ms 187900 KB Output is correct
22 Correct 2043 ms 189124 KB Output is correct
23 Correct 1819 ms 173408 KB Output is correct
24 Correct 1205 ms 195104 KB Output is correct
25 Correct 1670 ms 172128 KB Output is correct
26 Correct 1870 ms 190764 KB Output is correct
27 Correct 4333 ms 214020 KB Output is correct
28 Correct 4963 ms 213204 KB Output is correct
29 Correct 5650 ms 222268 KB Output is correct
30 Correct 4229 ms 213052 KB Output is correct
31 Correct 5862 ms 229736 KB Output is correct
32 Correct 5751 ms 228032 KB Output is correct
33 Correct 1239 ms 196356 KB Output is correct
34 Correct 4672 ms 211428 KB Output is correct
35 Correct 5495 ms 230216 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 41 ms 64980 KB Output is correct
3 Correct 468 ms 64980 KB Output is correct
4 Correct 34 ms 65016 KB Output is correct
5 Correct 49 ms 64948 KB Output is correct
6 Correct 32 ms 65028 KB Output is correct
7 Correct 1684 ms 127912 KB Output is correct
8 Correct 1757 ms 182404 KB Output is correct
9 Correct 1516 ms 169632 KB Output is correct
10 Correct 1849 ms 192072 KB Output is correct
11 Correct 1802 ms 192012 KB Output is correct
12 Correct 29 ms 64972 KB Output is correct
13 Correct 1645 ms 170804 KB Output is correct
14 Correct 1236 ms 195032 KB Output is correct
15 Correct 1641 ms 170820 KB Output is correct
16 Correct 1912 ms 190400 KB Output is correct
17 Correct 1686 ms 172056 KB Output is correct
18 Correct 1821 ms 173124 KB Output is correct
19 Correct 1816 ms 183244 KB Output is correct
20 Correct 1597 ms 171848 KB Output is correct
21 Correct 1901 ms 187900 KB Output is correct
22 Correct 2043 ms 189124 KB Output is correct
23 Correct 1819 ms 173408 KB Output is correct
24 Correct 1205 ms 195104 KB Output is correct
25 Correct 1670 ms 172128 KB Output is correct
26 Correct 1870 ms 190764 KB Output is correct
27 Correct 4333 ms 214020 KB Output is correct
28 Correct 4963 ms 213204 KB Output is correct
29 Correct 5650 ms 222268 KB Output is correct
30 Correct 4229 ms 213052 KB Output is correct
31 Correct 5862 ms 229736 KB Output is correct
32 Correct 5751 ms 228032 KB Output is correct
33 Correct 1239 ms 196356 KB Output is correct
34 Correct 4672 ms 211428 KB Output is correct
35 Correct 5495 ms 230216 KB Output is correct
36 Execution timed out 9045 ms 345028 KB Time limit exceeded
37 Halted 0 ms 0 KB -