제출 #415864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415864		koioi.org-koosaga	Escape Route (JOI21_escape_route)	C++17	70 / 100	9211 ms	1168924 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 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];
pi gph[96][96];

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

void Do(int n){
    for(int u = 0; u < n; u++){
        for(int v = 0; v < n; v++){
            if(gph[u][v].first == -1) continue;
            vector<lint> dist1(n, -3e18), dist2(n, 3e18);
            // backward shortest path
            {
                dist1[u] = gph[u][v].second - gph[u][v].first;
                vector<int> vis(n);
                for(int it = 0; it < n; it++){
                    pi ret(-5e18, 5e18);
                    for(int i = 0; i < n; i++){
                        if(!vis[i]) ret = max(ret, pi(dist1[i], i));
                    }
                    if(ret.first < 0) break;
                    int x = ret.second;
                    vis[x] = 1;
                    for(int i = 0; i < n; i++){
                        lint L = gph[x][i].first;
                        lint C = gph[x][i].second;
                        if(L == -1) continue;
                        if(dist1[i] < dist1[x] - L && dist1[x] < C){
                            dist1[i] = dist1[x] - L;
                        }
                    }
                }
            }
            // forward shortest path
            {
                dist2[v] = gph[u][v].second;
                vector<int> vis(n);
                for(int it = 0; it < n; it++){
                    pi ret(5e18, 5e18);
                    for(int i = 0; i < n; i++){
                        if(!vis[i]) ret = min(ret, pi(dist2[i], i));
                    }
                    int x = ret.second;
                    if(ret.first > S) break;
                    vis[x] = 1;
                    for(int i = 0; i < n; i++){
                        lint L = gph[x][i].first;
                        lint C = gph[x][i].second;
                        if(L == -1) continue;
                        if(dist2[i] > dist2[x] + L && dist2[x] + L <= C){
                            dist2[i] = dist2[x] + L;
                        }
                    }
                }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(dist2[j] <= S && dist1[i] >= 0){
                        prec[i][j].emplace_back(dist1[i], dist2[j] - dist1[i]);
                    }
                }
            }
        }
    }
}

// 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 < N; i++){
		for(int j = 0; j < N; j++){
			gph[i][j] = pi(-1, -1);
		}
	}
	for(int i = 0; i < M; i++){
		gph[A[i]][B[i]] = gph[B[i]][A[i]] = pi(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(int i = 0; i < N; i++){
				lint L = gph[x.j][i].first;
				lint C = gph[x.j][i].second;
				if(L == -1) continue;
				if(x.max_time + L <= C) enq(x.i, i, x.max_time + 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(int i = 0; i < N; i++){
				lint L = gph[x.i][i].first;
				lint C = gph[x.i][i].second;
				if(L == -1) continue;
				lint val = min(x.max_time, C) - L;
				if(val >= 0) enq(i, 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]);
                }
            }
        }
    }
    Do(N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            auto aux = prec[i][j];
            sort(all(aux));
            reverse(all(aux));
            prec[i][j].clear();
            for(auto &x : aux){
                if(sz(prec[i][j]) && prec[i][j].back().second <= x.second) continue;
                prec[i][j].push_back(x);
            }
            reverse(all(prec[i][j]));
        }
    }
    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));
            ans[i] = 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: 35 / 35
• Subtask 5: 0 / 30