제출 #1209559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209559		PenguinsAreCute	Escape Route (JOI21_escape_route)	C++17	5 / 100	9086 ms	112104 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<tuple<int,ll,ll>> adj[42];
ll S;
ll tim[42];
void dijkstra(int s, ll t) {
	memset(tim,69,sizeof(tim));
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	tim[s] = t;
	pq.push({t, s});
	while(pq.size()) {
		auto [d, x] = pq.top();
		pq.pop();
		if(d != tim[x])
			continue;
		for(auto [y, l, c]: adj[x]) {
			ll nwT = tim[x];
			if((nwT % S) <= c - l)
				nwT += l;
			else
				nwT = (nwT + S - 1) / S * S + l;
			if(nwT < tim[y]) {
				tim[y] = nwT;
				pq.push({nwT,y});
			}
		}
	}
}
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) {
	::S = S;
	for(int i=0;i<M;i++) {
		adj[A[i]].push_back({B[i],L[i],C[i]});
		adj[B[i]].push_back({A[i],L[i],C[i]});
	}
	vector<ll> ans;
	for(int i=0;i<Q;i++) {
		dijkstra(U[i], T[i]);
		ans.push_back(tim[V[i]] - T[i]);
	}
	return ans;
}

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