oj.uz

Submission #879107

# Submission time Handle Problem Language Result Execution time Memory
879107 2023-11-26T11:29:27 Z willychan Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 154964 KB 
#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Ba = 90; bitset<Ba> reach[90];
ll dis[90][90];
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) {
	vector<vector<pair<int,int> >> side(N);
	for(int i=0;i<M;i++){
		side[A[i]].push_back({B[i],i});
		side[B[i]].push_back({A[i],i});
	}
	for(int i=0;i<N;i++) reach[i].reset();

	// pre	
		for(int s=0;s<N;s++){
			for(int i=0;i<N;i++) dis[s][i]=1e17;
			dis[s][s]=0;
			priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> >> pq;
			pq.push({0,s});
			while(pq.size()){
				auto cur = pq.top();
				pq.pop();
				if(dis[s][cur.second]!=cur.first) continue;
				for(auto e : side[cur.second]){
					int mind = e.second;
					if(C[mind]-L[mind]<cur.first) continue;
					if(dis[s][e.first]>cur.first+L[mind]){
						dis[s][e.first] = cur.first+L[mind];
						pq.push({dis[s][e.first],e.first});
					}
				}
			}
		}
	// preend
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++)
			if(dis[i][j]<S) reach[i][j]=1;
	}
	vector<ll>  ans(Q);
	for(int q=0;q<Q;q++){
		vector<ll> qdis(N,1e18);
		qdis[U[q]]=0;
		priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> >> pq;
		pq.push({0,U[q]});
		while(pq.size()){
			auto cur = pq.top();
			pq.pop();
			if(qdis[cur.second]!=cur.first) continue;
			for(auto e : side[cur.second]){
				int mind = e.second;
				if(C[mind]-L[mind]-T[q]<cur.first) continue;
				if(qdis[e.first]>cur.first+L[mind]){
					qdis[e.first] = cur.first+L[mind];
					pq.push({qdis[e.first],e.first});
				}
			}
		}
		for(int i=0;i<N;i++) if(qdis[i]>S-T[q]) qdis[i]=1e18;
		if(qdis[V[q]]<1e18){
			ans[q] = qdis[V[q]];
			continue;
		}
		ll qans = 1e18;
		queue<pair<int,int> > que;
		bitset<Ba> reachq;
		for(int i=0;i<N;i++){
			if(qdis[i]<1e18 && !reachq[i]) {
				que.push({i,1});
				reachq[i]=1;
			}
		}
		while(que.size()){
			auto cur = que.front();
			que.pop();
			if(dis[cur.first][V[q]]<1e18) qans = min(qans,(S*cur.second)+dis[cur.first][V[q]]);
			for(int j=0;j<N;j++){
				if(reach[cur.first][j] && !reachq[j]){
					que.push({j,cur.second+1});
					reachq[j]=1;
				}
			}
		}
		ans[q] = qans-T[q];
	}



  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65092 KB Output is correct
2 Correct 12 ms 65112 KB Output is correct
3 Correct 22 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 13 ms 65056 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9045 ms 154964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65092 KB Output is correct
2 Correct 12 ms 65112 KB Output is correct
3 Correct 22 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 13 ms 65056 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Execution timed out 9045 ms 154964 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65092 KB Output is correct
2 Correct 12 ms 65112 KB Output is correct
3 Correct 22 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 13 ms 65056 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Execution timed out 9045 ms 154964 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65092 KB Output is correct
2 Correct 12 ms 65112 KB Output is correct
3 Correct 22 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 13 ms 65056 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Execution timed out 9045 ms 154964 KB Time limit exceeded
8 Halted 0 ms 0 KB -