Submission #1157708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157708		dibamboo23	Escape Route (JOI21_escape_route)	C++20	0 / 100	103 ms	135488 KiB

escape_route

#include <bits/stdc++.h>

#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;
	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){
				p[to]=val;
				st.insert({p[to],to});
			}
		}
	}
}

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)
{
	day=S;
	n=N;
	int m=M,q=Q;
	vector<ll>ans;
	for(int i=0;i<m;i++){
		add_edge(A[i],B[i],i);
		start[i]=C[i];
		len[i]=L[i];
	}
	for(int i=0;i<q;i++){
		ans.push_back(calc(U[i],V[i],T[i]));
	}
	return ans;
}

// signed main(){}

Compilation message (stderr)

escape_route.cpp: In function 'long long int calc(int, int, long long int)':
escape_route.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
   41 | }
      | ^

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