Submission #415764

#	Time	Username	Problem	Language	Result	Execution time	Memory
415764		koioi.org-koosaga	Escape Route (JOI21_escape_route)	C++17	35 / 100	9020 ms	196984 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;

struct edg{
	int pos;
	lint L, C;
};

struct node{
	int i, j; lint max_time;
	bool operator<(const node &n)const{
		return max_time < n.max_time;
	}
};

lint daybreak[96][96];
lint dayfinish[96][96];
lint adj[96][96], dp[96][96];
vector<edg> gph[96];

vector<pi> prec[96][96];
lint S;

void do_prec(int s, int n){
	priority_queue<pi, vector<pi>, greater<pi>> pq[96]; // (dist, weight)
	pq[s].emplace(0, -S);
	for(int i = 0; i < n; i++) prec[s][i].emplace_back(-1, 1);
	while(true){
		pi ans(1e18, 1e18);
		for(int i = 0; i < n; i++){
			while(sz(pq[i]) &&
				(pq[i].top().first <= prec[s][i].back().first ||
				-pq[i].top().second <= -prec[s][i].back().second)) pq[i].pop();

			if(sz(pq[i])){
				ans = min(ans, pi(pq[i].top().first, i));
			}
		}
		if(ans.second > n) break;
		int pos = ans.second;
		prec[s][pos].push_back(pq[pos].top());
		lint cur_dist = pq[pos].top().first;
		lint cur_weight = -pq[pos].top().second;
		pq[pos].pop();
		for(auto &j : gph[pos]){
			lint new_dist = cur_dist + j.L;
			lint new_weight = min(cur_weight, j.C - new_dist);
			if(new_weight < 0) continue;
			pq[j.pos].emplace(new_dist, -new_weight);
		}
	}
	for(int i = 0; i < n; i++){
		for(auto &[x, y] : prec[s][i]){
	//		printf("prev %d %d %lld %lld\n", s, i, x, y);
			tie(x, y) = pi(-y, x);
		}
		for(int j = 0; j < sz(prec[s][i])-1; j++){
			prec[s][i][j].second = prec[s][i][j + 1].second;
		}
		prec[s][i].back().second = 1e18;
		for(auto &[x, y] : prec[s][i]){
			x++;
	//		printf("%d %d %lld %lld\n", s, i, x, y);
		}
	}
}

// wtf just use namespace std and pairs
std::vector<long long> calculate_necessary_time(
		int N, int M, long long Sfuck, 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) {
	S = Sfuck;
	for(int i = 0; i < M; i++){
		gph[A[i]].push_back({B[i], L[i], C[i]});
		gph[B[i]].push_back({A[i], L[i], C[i]});
	}
	{
		priority_queue<node> pq;
		memset(daybreak, 0x3f, sizeof(daybreak));
		auto enq = [&](int s, int e, lint x){
			if(daybreak[s][e] > x){
				daybreak[s][e] = x;
				pq.push({s, e, -x});
			}
		};
		for(int i = 0; i < N; i++){
			enq(i, i, 0);
		}
		while(sz(pq)){
			auto x = pq.top(); pq.pop();
			x.max_time = -x.max_time;
			if(daybreak[x.i][x.j] != x.max_time) continue;
			for(auto &e : gph[x.j]){
				if(x.max_time + e.L <= e.C){
					enq(x.i, e.pos, x.max_time + e.L);
				}
			}
		}
	}
	{
		priority_queue<node> pq;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				dayfinish[i][j] = -1e18;
			}
		}
		auto enq = [&](int s, int e, lint x){
			if(dayfinish[s][e] < x){
				dayfinish[s][e] = x;
				pq.push({s, e, x});
			}
		};
		for(int i = 0; i < N; i++){
			enq(i, i, S);
		}
		while(sz(pq)){
			auto x = pq.top(); pq.pop();
			if(dayfinish[x.i][x.j] != x.max_time) continue;
			for(auto &e : gph[x.i]){
				lint val = min(x.max_time, e.C) - e.L;
				if(val >= 0) enq(e.pos, x.j, val);
			}
		}
	}
	{
		memset(adj, 0x3f, sizeof(adj));
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(dayfinish[i][j] >= 0) adj[i][j] = 1;
				if(i == j) adj[i][j] = 0;
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				for(int k = 0; k < N; k++){
					adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
				}
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				assert(adj[i][j] <= N);
				dp[i][j] = 1e18;
				for(int k = 0; k < N; k++){
					dp[i][j] = min(adj[i][k] * S + daybreak[k][j], dp[i][j]);
				}
			}
		}
	}
	for(int i = 0; i < N; i++){
		do_prec(i, N);
	}
	vector<lint> ans(Q);
	for(int i = 0; i < Q; i++){
		if(dayfinish[U[i]][V[i]] >= T[i]){
			auto it = upper_bound(all(prec[U[i]][V[i]]), pi(T[i] + 1, -1));
			ans[i] = prev(it)->second;
			continue;
		}
		lint ret = 1e18;
		for(int j = 0; j < N; j++){
			if(dayfinish[U[i]][j] >= T[i]){
				ret = min(ret, S - T[i] + dp[j][V[i]]);
			}
		}
		ans[i] = ret;
	}
	return ans;
}

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