Submission #519437

#	Time	Username	Problem	Language	Result	Execution time	Memory
519437		fatemetmhr	Escape Route (JOI21_escape_route)	C++17	0 / 100	2117 ms	188532 KiB

escape_route

//  ~Be name khoda~  //

#include "escape_route.h"
#include<bits/stdc++.h>

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  91;
const int maxq  =  3e6   + 5;
const int maxe  =  4e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

ll t[maxq], c[maxe], l[maxe];
int u[maxq], v[maxq];
int a[maxe], b[maxe];
int n, m, q;
ll s, ans[maxq], mn, tim[maxn5];
bool ok[maxn5], done[maxn5];
ll dis[maxn5], with0[maxn5][maxn5];
int adj[maxn5][maxn5];
vector <int> av[maxn5];

inline bool cmp(int i, int j){return t[i] < t[j];}

inline void fix(ll &a){
	if(a >= s)
		a -= s;
}

inline void dij(int v, ll ti){
	//cout << "hola " << v << ' ' << ti << endl;
	memset(dis, -1, sizeof dis);
	memset(done, false, sizeof done);
	memset(ok, false, sizeof ok);
	dis[v] = 0;
	tim[v] = ti;
	ok[v] = true;
	
	
	mn = inf;
	for(int i = 0; i < n; i++){
		int v = -1;
		for(int j = 0; j < n; j++) if(!done[j] && dis[j] > -1 && (v == -1 || dis[j] < dis[v])){
			v = j;
		}
		done[v] = true;
		//cout << "ok " << v << ' ' << dis[v] << ' ' << tim[v] << endl;
		for(int j = 0; j < n; j++) if(adj[v][j] != -1 && !done[j]){
			ll len;
			if(tim[v] <= c[adj[v][j]] - l[adj[v][j]]){
				if(ok[v]){
					ok[j] = true;
					mn = min(mn, c[adj[v][j]] - l[adj[v][j]] - tim[v]);
				}
				len = l[adj[v][j]];
			}
			else{
				len = s - tim[v] + l[adj[v][j]];
			}
			//cout << v << ' ' << j << ' ' << len << ' ' << adj[v][j] << ' ' << l[adj[v][j]] << endl;
			if(dis[j] == -1 || dis[j] > dis[v] + len){
				dis[j] = dis[v] + len;
				tim[j] = tim[v] + len;
				fix(tim[j]);
			}
		}
	}
	return;
}

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) {
    
    n = N;
    m = M;
    s = S;
    q = Q;
    memset(adj, -1, sizeof adj);
    for(int i = 0; i < m; i++){
    	a[i] = A[i];
    	b[i] = B[i];
    	l[i] = L[i];
    	c[i] = C[i];
    	adj[a[i]][b[i]] = adj[b[i]][a[i]] = i;
    }
    for(int i = 0; i < q; i++){
    	u[i] = U[i];
    	v[i] = V[i];
    	t[i] = T[i];
    	av[u[i]].pb(i);
    }
    //*
    for(int i = 0; i < n; i++){
    	dij(i, 0);
    	for(int j = 0; j < n; j++)
    		with0[i][j] = dis[j];
    }
    //*/
    
    for(int i = 0; i < n; i++){
    	sort(all(av[i]), cmp);
    	ll last = 0;
    	dij(i, 0);
    	for(auto j : av[i]){
    		if(rng() % 5 > 0 && mn < t[j] - last){
    			last = t[j];
    			dij(i, last);
    			ans[j] = dis[v[j]];
    		}
    		else{
    			mn -= (t[j] - last);
    			ans[j] = inf;
    			for(int z = 0; z < n; z++) if(ok[z]){
    				if(z == v[j])
    					ans[j] = min(ans[j], dis[z]);
    				ans[j] = min(ans[j], dis[z] + s - (tim[z] + (t[j] - last)) + with0[z][v[j]]);
    			}
    		}
    	}
    }
    
    vector <long long> ret;
    for(int i = 0; i < q; i++)
    	ret.pb(ans[i]);
    
    return ret;
}

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