Submission #1209586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209586		emptypringlescan	Escape Route (JOI21_escape_route)	C++17	0 / 100	235 ms	112500 KiB

escape_route

#include "escape_route.h"
#pragma GCC optize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
int n,m,q;
long long mod;
vector<pair<int,pair<long long,long long> > > adj[95];
long long stz[95][95];
vector<pair<long long,long long> > tim[95][95],dir[95][95];
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; mod=S; q=Q;
	for(int i=0; i<m; i++){
		int a,b;
		long long c,d;
		a=A[i]; b=B[i]; c=L[i]; d=C[i];
		adj[a].push_back({b,{c,d}});
		adj[b].push_back({a,{c,d}});
	}
	queue<pair<long long,pair<long long,int> > > pq;
	for(int i=0; i<95; i++){
		for(int j=0; j<95; j++) stz[i][j]=1e18;
	}
	for(int i=0; i<n; i++){
		pq.push({0,{0,i}});
		stz[i][i]=0;
		while(!pq.empty()){
			long long a=pq.front().first,b=pq.front().second.first;
			int c=pq.front().second.second;
			pq.pop();
			if(a>stz[i][c]) continue;
			for(auto j:adj[c]){
				long long nc=a+j.second.first;
				if(a%mod>j.second.second-j.second.first) nc=(a/mod+1)*mod+j.second.first;
				if(stz[i][j.first]>nc){
					pq.push({nc,{nc,j.first}});
					stz[i][j.first]=nc;
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++) pq.push({stz[j][i],{-mod,j}});
		while(!pq.empty()){
			long long a=pq.front().first,b=-pq.front().second.first;
			int c=pq.front().second.second;
			pq.pop();
			if(!tim[c][i].empty()&&tim[c][i].back().first>=b) continue;
			tim[c][i].push_back({b,a});
			for(auto j:adj[c]){
				long long nt=min(b,j.second.second)-j.second.first;
				if(nt<0) continue;
				if(!tim[j.first][i].empty()&&tim[j.first][i].back().first>=nt) continue;
				pq.push({a,{-nt,j.first}});
			}
		}
	}
	for(int i=0; i<n; i++){
		pq.push({0,{mod,i}});
		while(!pq.empty()){
			long long a=pq.front().first,b=pq.front().second.first;
			int c=pq.front().second.second;
			pq.pop();
			if(!dir[c][i].empty()&&dir[c][i].back().first>=b) continue;
			dir[c][i].push_back({b,a});
			for(auto j:adj[c]){
				long long nc=a+j.second.first;
				long long nt=min(b,j.second.second)-j.second.first;
				if(nt<0) continue;
				if(!dir[j.first][i].empty()&&dir[j.first][i].back().first>=nt) continue;
				pq.push({nc,{nt,j.first}});
			}
		}
	}/*
	for(int i=0; i<n; i++){
		for(int o=0; o<n; o++){
			cout << i << " to " << o << '\n';
			for(auto j:tim[i][o]) cout << j.first << ' ' << j.second << "   ";
			cout << '\n';
		}
		cout << '\n';
	}*/
	vector<long long> ans(q);
	for(int i=0; i<q; i++){
		int a,b;
		long long c;
		a=U[i]; b=V[i]; c=T[i];
		pair<long long,long long> wt=*lower_bound(tim[a][b].begin(),tim[a][b].end(),make_pair(c,-1ll));
		long long c1=wt.second+mod-c;
		long long c2=1e18;
		if(!dir[a][b].empty()&&dir[a][b].back().first>=c) c2=lower_bound(dir[a][b].begin(),dir[a][b].end(),make_pair(c,-1ll))->second;
		ans[i]=min(c1,c2);
	}
  return ans;
}

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