Submission #427900

#	Time	Username	Problem	Language	Result	Execution time	Memory
427900		amoo_safar	Escape Route (JOI21_escape_route)	C++17	5 / 100	9071 ms	154960 KiB

escape_route

#include "escape_route.h"

#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

const int N = 92;

int n, m;
ll S;

vi A, B;
vl L, C;
vector<int> G[N];

ll dis[N], mk[N];

void Djik(int src, ll st){
	memset(dis, 31, sizeof dis);
	memset(mk, 0, sizeof mk);
	dis[src] = st;
	int adj;
	ll w;
	for(int _ = 0; _ < n; _++){
		int idx = -1;
		for(int i = 0; i < n; i++) if(!mk[i]) idx = i;
		if(idx == -1) continue;
		for(int i = 0; i < n; i++) if(!mk[i] && dis[i] < dis[idx]) idx = i;
		mk[idx] = 1;
		for(auto e : G[idx]){
			adj = A[e] ^ B[e] ^ idx;
			if(dis[idx] % S <= C[e] - L[e])
				w = dis[idx] + L[e];
			else 
				w = dis[idx] + (S - (dis[idx] % S)) + L[e];
			if(w < dis[adj])
				dis[adj] = w;
		}
	}
}

vl calculate_necessary_time(int _n, int _m, ll _S, int Q, vi _A, vi _B, vl _L, vl _C, vi _U, vi _V, vl _T) {
	n = _n; m = _m; S = _S;
	A = _A; B = _B; L = _L; C = _C;
	for(int i = 0; i < m; i++)
		G[A[i]].pb(i), G[B[i]].pb(i);

	vl ANS;
	for(int i = 0; i < Q; i++){
		Djik(_U[i], _T[i]);
		ANS.pb(dis[_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