oj.uz

Submission #439633

# Submission time Handle Problem Language Result Execution time Memory
439633 2021-06-30T11:41:28 Z kig9981 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 221184 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<tuple<long long,int,int>> qry[91];
long long CC[91][91], LL[91][91], D[91], PV[91];
int L[92], R[92], P[91];

void dijk(int N, long long S, int r, long long B)
{
	memset(PV,0x7f,sizeof(PV));
	memset(D,0x7f,sizeof(D));
	D[r]=B;
	R[0]=1; L[N+1]=N;
	for(int i=1;i<=N;i++) {
		L[i]=i-1;
		R[i]=i+1;
	}
	P[r]=r;
	for(int t=0;t<N;t++) {
		long long mx=INF;
		int c=r;
		for(int j=R[0];j<=N;j=R[j]) if(mx>D[j]) {
			mx=D[j];
			c=j;
		}
		L[R[c]]=L[c];
		R[L[c]]=R[c];
		PV[c]=min(PV[c],PV[P[c]]);
		for(int j=R[0];j<=N;j=R[j]) if(CC[c][j] && D[j]>(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j]) {
			D[j]=(D[c]%S<=CC[c][j]-LL[c][j] ? D[c]:(D[c]+S-1)/S*S)+LL[c][j];
			P[j]=c;
			if(D[j]<S) PV[j]=CC[c][j]+1-LL[c][j]-D[c];
		}
	}
}

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(Q);
	for(int i=0;i<M;i++) {
		A[i]++; B[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 i=0;i<Q;i++) qry[++U[i]].emplace_back(T[i],++V[i],i);
	for(int r=1;r<=N;r++) {
		long long BB=0;
		dijk(N,S,r,0);
		sort(qry[r].rbegin(),qry[r].rend());
		while(qry[r].size()) {
			auto[t,v,i]=qry[r].back();
			qry[r].pop_back();
			if(t>=BB+PV[v]) dijk(N,S,r,BB=t);
			ret[i]=D[v]-(D[v]<S ? BB:t);
		}
	}
	return ret;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64968 KB Output is correct
2 Correct 30 ms 65016 KB Output is correct
3 Correct 37 ms 64988 KB Output is correct
4 Correct 28 ms 65024 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 153084 KB Output is correct
2 Correct 863 ms 191920 KB Output is correct
3 Correct 789 ms 179436 KB Output is correct
4 Correct 854 ms 201660 KB Output is correct
5 Correct 874 ms 204152 KB Output is correct
6 Correct 31 ms 64972 KB Output is correct
7 Correct 807 ms 196420 KB Output is correct
8 Correct 931 ms 221184 KB Output is correct
9 Correct 789 ms 188112 KB Output is correct
10 Correct 910 ms 209088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64968 KB Output is correct
2 Correct 30 ms 65016 KB Output is correct
3 Correct 37 ms 64988 KB Output is correct
4 Correct 28 ms 65024 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 779 ms 153084 KB Output is correct
8 Correct 863 ms 191920 KB Output is correct
9 Correct 789 ms 179436 KB Output is correct
10 Correct 854 ms 201660 KB Output is correct
11 Correct 874 ms 204152 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 807 ms 196420 KB Output is correct
14 Correct 931 ms 221184 KB Output is correct
15 Correct 789 ms 188112 KB Output is correct
16 Correct 910 ms 209088 KB Output is correct
17 Correct 970 ms 199500 KB Output is correct
18 Correct 998 ms 198152 KB Output is correct
19 Correct 1074 ms 207024 KB Output is correct
20 Correct 748 ms 202608 KB Output is correct
21 Correct 1094 ms 210628 KB Output is correct
22 Correct 1088 ms 193192 KB Output is correct
23 Correct 782 ms 201864 KB Output is correct
24 Correct 823 ms 204148 KB Output is correct
25 Correct 930 ms 174988 KB Output is correct
26 Correct 1111 ms 187188 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64968 KB Output is correct
2 Correct 30 ms 65016 KB Output is correct
3 Correct 37 ms 64988 KB Output is correct
4 Correct 28 ms 65024 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 779 ms 153084 KB Output is correct
8 Correct 863 ms 191920 KB Output is correct
9 Correct 789 ms 179436 KB Output is correct
10 Correct 854 ms 201660 KB Output is correct
11 Correct 874 ms 204152 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 807 ms 196420 KB Output is correct
14 Correct 931 ms 221184 KB Output is correct
15 Correct 789 ms 188112 KB Output is correct
16 Correct 910 ms 209088 KB Output is correct
17 Correct 970 ms 199500 KB Output is correct
18 Correct 998 ms 198152 KB Output is correct
19 Correct 1074 ms 207024 KB Output is correct
20 Correct 748 ms 202608 KB Output is correct
21 Correct 1094 ms 210628 KB Output is correct
22 Correct 1088 ms 193192 KB Output is correct
23 Correct 782 ms 201864 KB Output is correct
24 Correct 823 ms 204148 KB Output is correct
25 Correct 930 ms 174988 KB Output is correct
26 Correct 1111 ms 187188 KB Output is correct
27 Correct 2144 ms 181320 KB Output is correct
28 Correct 2518 ms 180164 KB Output is correct
29 Correct 2256 ms 185300 KB Output is correct
30 Correct 771 ms 180692 KB Output is correct
31 Correct 2700 ms 180508 KB Output is correct
32 Correct 2744 ms 179184 KB Output is correct
33 Correct 827 ms 191820 KB Output is correct
34 Correct 1976 ms 150424 KB Output is correct
35 Correct 2676 ms 174676 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64968 KB Output is correct
2 Correct 30 ms 65016 KB Output is correct
3 Correct 37 ms 64988 KB Output is correct
4 Correct 28 ms 65024 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 779 ms 153084 KB Output is correct
8 Correct 863 ms 191920 KB Output is correct
9 Correct 789 ms 179436 KB Output is correct
10 Correct 854 ms 201660 KB Output is correct
11 Correct 874 ms 204152 KB Output is correct
12 Correct 31 ms 64972 KB Output is correct
13 Correct 807 ms 196420 KB Output is correct
14 Correct 931 ms 221184 KB Output is correct
15 Correct 789 ms 188112 KB Output is correct
16 Correct 910 ms 209088 KB Output is correct
17 Correct 970 ms 199500 KB Output is correct
18 Correct 998 ms 198152 KB Output is correct
19 Correct 1074 ms 207024 KB Output is correct
20 Correct 748 ms 202608 KB Output is correct
21 Correct 1094 ms 210628 KB Output is correct
22 Correct 1088 ms 193192 KB Output is correct
23 Correct 782 ms 201864 KB Output is correct
24 Correct 823 ms 204148 KB Output is correct
25 Correct 930 ms 174988 KB Output is correct
26 Correct 1111 ms 187188 KB Output is correct
27 Correct 2144 ms 181320 KB Output is correct
28 Correct 2518 ms 180164 KB Output is correct
29 Correct 2256 ms 185300 KB Output is correct
30 Correct 771 ms 180692 KB Output is correct
31 Correct 2700 ms 180508 KB Output is correct
32 Correct 2744 ms 179184 KB Output is correct
33 Correct 827 ms 191820 KB Output is correct
34 Correct 1976 ms 150424 KB Output is correct
35 Correct 2676 ms 174676 KB Output is correct
36 Execution timed out 9019 ms 122992 KB Time limit exceeded
37 Halted 0 ms 0 KB -