oj.uz

Submission #439613

# Submission time Handle Problem Language Result Execution time Memory
439613 2021-06-30T10:54:24 Z kig9981 Escape Route (JOI21_escape_route) C++17
5 / 100
 875 ms 111996 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const long long INF=0x7f7f7f7f7f7f7f7fLL;
vector<long long> x[90];
long long D[90][180][90], CC[90][90], LL[90][90], P[90];
bool chk[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<long long> ret;
	memset(D,0x7f,sizeof(D));
	for(int i=0;i<M;i++) {
		LL[A[i]][B[i]]=LL[B[i]][A[i]]=L[i];
		CC[A[i]][B[i]]=CC[B[i]][A[i]]=C[i];
	}
	for(int r=0;r<N;r++) {
		x[r].push_back(0);
		for(int i=0;;i++) {
			long long O=INF;
			D[r][i][r]=x[r][i];
			memset(chk,0,sizeof(chk));
			memset(P,0x7f,sizeof(P));
			for(int t=0;t<N;t++) {
				long long mx=INF;
				int c=r;
				for(int j=0;j<N;j++) if(!chk[j] && mx>D[r][i][j]) {
					mx=D[r][i][j];
					c=j;
				}
				chk[c]=true;
				O=min(O,P[c]);
				for(int j=0;j<N;j++) if(!chk[j] && CC[c][j] && D[r][i][j]>(D[r][i][c]%S<=CC[c][j]-LL[c][j] ? D[r][i][c]:(D[r][i][c]+S-1)/S*S)+LL[c][j]) {
					D[r][i][j]=(D[r][i][c]%S<=CC[c][j]-LL[c][j] ? D[r][i][c]:(D[r][i][c]+S-1)/S*S)+LL[c][j];
					if(D[r][i][j]<S) P[j]=CC[c][j]+1-LL[c][j]-D[r][i][c];
				}
			}
			if(O==INF) break;
			x[r].push_back(x[r].back()+O);
		}
	}
	for(int i=0;i<Q;i++) {
		int j=upper_bound(x[U[i]].begin(),x[U[i]].end(),T[i])-x[U[i]].begin()-1;
		ret.push_back(D[U[i]][j][V[i]]-(D[U[i]][j][V[i]]<S ? x[U[i]][j]:T[i]));
	}
	return ret;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64964 KB Output is correct
2 Correct 50 ms 65016 KB Output is correct
3 Correct 105 ms 64952 KB Output is correct
4 Correct 36 ms 65048 KB Output is correct
5 Correct 37 ms 65028 KB Output is correct
6 Correct 35 ms 64940 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 875 ms 111996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64964 KB Output is correct
2 Correct 50 ms 65016 KB Output is correct
3 Correct 105 ms 64952 KB Output is correct
4 Correct 36 ms 65048 KB Output is correct
5 Correct 37 ms 65028 KB Output is correct
6 Correct 35 ms 64940 KB Output is correct
7 Incorrect 875 ms 111996 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64964 KB Output is correct
2 Correct 50 ms 65016 KB Output is correct
3 Correct 105 ms 64952 KB Output is correct
4 Correct 36 ms 65048 KB Output is correct
5 Correct 37 ms 65028 KB Output is correct
6 Correct 35 ms 64940 KB Output is correct
7 Incorrect 875 ms 111996 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64964 KB Output is correct
2 Correct 50 ms 65016 KB Output is correct
3 Correct 105 ms 64952 KB Output is correct
4 Correct 36 ms 65048 KB Output is correct
5 Correct 37 ms 65028 KB Output is correct
6 Correct 35 ms 64940 KB Output is correct
7 Incorrect 875 ms 111996 KB Output isn't correct
8 Halted 0 ms 0 KB -