Submission #1157768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157768		dibamboo23	Escape Route (JOI21_escape_route)	C++20	5 / 100	9085 ms	135632 KiB

escape_route

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

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


#define ll long long
#define sz size()
#define F first
#define S second

using namespace std;

const int N=1e6+3;
const ll inf=1e18;

ll start[N];// when security inspection start on edge
ll len[N];// length of edge
vector<pair<int,int>>g[N];// our graph [vertex , index of edge]
int n;// number of vertex
ll day;

void add_edge(int A,int B,int id){
	g[A].push_back({B,id});
	g[B].push_back({A,id});
}

ll calc(int s,int f,ll t){
	vector<ll>p(n+3,inf);
	p[s]=t;
	set<pair<ll,int>>st;
	st.insert({p[s],s});
	while(!st.empty()){
		int v=st.begin()->S;
		st.erase(st.begin());
		for(auto [to,i]:g[v]){
			ll val=inf;
			if((p[v]%day)+len[i]<=start[i])val=p[v]+len[i];
			else val=(p[v]/day+1)*day+len[i];
			if(p[to]>val){
				st.erase({p[to],to});
				p[to]=val;
				st.insert({p[to],to});
			}
		}
	}
	// for(int i=0;i<n;i++)cout<<p[i]<<" ";
	// cout<<"\n";
	return p[f]-t;
}

std::vector<long long> calculate_necessary_time(
    signed N, signed M, long long S, signed Q, std::vector<signed> A, std::vector<signed> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<signed> U,
    std::vector<signed> V, std::vector<long long> T)
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	day=S;
	n=N;
	// cout<<day<<" "<<n<<"\n";
	int m=M,q=Q;
	vector<ll>ans;
	for(int i=0;i<m;i++){
		// cout<<A[i]<<" "<<B[i]<<" "<<i<<"\n"; 
		add_edge(A[i],B[i],i);
		start[i]=C[i];
		len[i]=L[i];
	}
	// for(int i=0;i<n;i++){
		// for(auto [to,ii]:g[i])cout<<i<<"-"<<to<<" "<<ii<<"\n";
	// }
	for(int i=0;i<q;i++){
		ans.push_back(calc(U[i],V[i],T[i]));
	}
	return ans;
}

// signed main(){
	// int N,M;ll S;int Q;
	// vector<int>A(M+3),B(M+3),U(Q+3),V(Q+3);
	// vector<ll>L(M+3),C(M+3),T(Q+3);
	// cin>>N>>M>>S>>Q;
	// for(int i=0;i<M;i++)cin>>A[i]>>B[i]>>L[i]>>C[i];
	// for(int i=0;i<Q;i++)cin>>U[i]>>V[i]>>T[i];
	// vector<ll>ans=calculate_necessary_time(N,M,S,Q,A,B,L,C,U,V,T);
	// for(auto to:ans)cout<<to<<"\n";
// }

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