Submission #735725

#	Time	Username	Problem	Language	Result	Execution time	Memory
735725		QwertyPi	Escape Route (JOI21_escape_route)	C++17	100 / 100	8819 ms	1231448 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define int long long
#define INF (1LL << 60)
using namespace std;

const int N = 91;

struct edge{
	int to, l, c;
};

vector<edge> G[N];

int S;

int norm(int tx){
	tx %= S;
	if(tx < 0) tx += S;
	return tx;
}

vector<pair<int, int>> Ti[N][N], Sc[N][N];
int D[N][N], La[N][N];

void add_data(int x, int y, int tx, int ty){
	if(tx <= -(INF >> 1) || ty >= (INF >> 1)) return;
	int rtx = norm(tx);
	int rty = ty + rtx - tx;
	int tot = rty - rtx;
	Ti[x][y].push_back({rtx, tot});
}

vector<int> from(int x, int t){
	vector<int> d(N, -INF); d[x] = t;
	priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
	pq.push({t, x});
	while(!pq.empty()){
		auto [t, v] = pq.top(); pq.pop(); 
		if(d[v] != t) continue;
		for(auto [to, l, c] : G[v]){
			int tp = norm(t), nt;
			if(tp > c){ // back to c
				nt = t - (tp - c) - l;
			}else if(tp >= l){ // ok
				nt = t - l;
			}else{ // no last day
				nt = -INF;
			}
			if(nt > d[to]){
				d[to] = nt;
				pq.push({nt, to});
			}
		}
	}
	return d;
}

vector<int> to(int x, int t, bool allow_midnight){
	vector<int> d(N, INF); d[x] = t;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({t, x});
	while(!pq.empty()){
		auto [t, v] = pq.top(); pq.pop();
		if(d[v] != t) continue;
		for(auto [to, l, c] : G[v]){
			int tp = norm(t), nt;
			if(tp > c - l){ // next day
				nt = allow_midnight ? t + (S - tp) + l : INF;
			}else{ // ok
				nt = t + l;
			}
			if(nt < d[to]){
				d[to] = nt;
				pq.push({nt, to});
			}
		}
	}
	return d;
}


vector<int> calculate_necessary_time(int32_t N, int32_t M, int S, int32_t Q,
									 vector<int32_t> A, vector<int32_t> B, vector<int> L, vector<int> C, 
									 vector<int32_t> U, vector<int32_t> V, vector<int> T) {
	
	::S = S;
	for(int i = 0; i < M; i++){
		G[A[i]].push_back({B[i], L[i], C[i]});
		G[B[i]].push_back({A[i], L[i], C[i]});
	}
	
	for(int i = 0; i < M; i++){
		vector<int> d1, d2;
		
		d1 = from(A[i], C[i] - L[i]);
		d2 = to(B[i], C[i], false);
		for(int x = 0; x < N; x++){
			for(int y = 0; y < N; y++){
				add_data(x, y, d1[x], d2[y]);
			}
		}
		
		d1 = from(B[i], C[i] - L[i]);
		d2 = to(A[i], C[i], false);
		for(int x = 0; x < N; x++){
			for(int y = 0; y < N; y++){
				add_data(x, y, d1[x], d2[y]);
			}
		}
	}
	
	for(int i = 0; i < N; i++){
		vector<int> d = to(i, 0, true);
		for(int j = 0; j < N; j++){
			D[i][j] = d[j];
		}
	}
	
	for(int u = 0; u < N; u++){
		for(int v = 0; v < N; v++){
			vector<pair<int, int>> vp;
			sort(Ti[u][v].begin(), Ti[u][v].end());
			for(auto [tx, tot] : Ti[u][v]){
				while(!vp.empty() && vp.back().second >= tot) vp.pop_back();
				if(!vp.empty() && vp.back().first == tx) continue;
				vp.push_back({tx, tot}); 
			}
			Ti[u][v] = vp;
		}
	}
	
	for(int u = 0; u < N; u++){
		for(int v = 0; v < N; v++){
			if(u != v) La[u][v] = Ti[u][v].empty() ? -1 : (--Ti[u][v].end())->first;
			else La[u][v] = S;
		}
	}
	
	for(int x = 0; x < N; x++){
		for(int y = 0; y < N; y++){
			for(int z = 0; z < N; z++){
				Sc[x][z].push_back({La[x][y], D[y][z]});
			}
		}
	}
	
	for(int u = 0; u < N; u++){
		for(int v = 0; v < N; v++){
			vector<pair<int, int>> vp;
			sort(Sc[u][v].begin(), Sc[u][v].end());
			for(auto [tx, tot] : Sc[u][v]){
				while(!vp.empty() && vp.back().second >= tot) vp.pop_back();
				if(!vp.empty() && vp.back().first == tx) continue;
				vp.push_back({tx, tot}); 
			}
			Sc[u][v] = vp;
		}
	}
	
	vector<int> ans(Q, INF);
	for(int i = 0; i < Q; i++){
		auto ptr = lower_bound(Ti[U[i]][V[i]].begin(), Ti[U[i]][V[i]].end(), pair<int, int>{T[i], 0});
		if(ptr != Ti[U[i]][V[i]].end()){
			ans[i] = min(ans[i], ptr->second);
		}
		
		ptr = lower_bound(Sc[U[i]][V[i]].begin(), Sc[U[i]][V[i]].end(), pair<int, int>{T[i], 0});
		if(ptr != Sc[U[i]][V[i]].end()){
			ans[i] = min(ans[i], ptr->second + S - T[i]);
		}
	}
	return ans; 
}

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