oj.uz

Submission #427900

# Submission time Handle Problem Language Result Execution time Memory
427900 2021-06-15T04:32:03 Z amoo_safar Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 154960 KB 
#include "escape_route.h"

#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

const int N = 92;

int n, m;
ll S;

vi A, B;
vl L, C;
vector<int> G[N];

ll dis[N], mk[N];

void Djik(int src, ll st){
	memset(dis, 31, sizeof dis);
	memset(mk, 0, sizeof mk);
	dis[src] = st;
	int adj;
	ll w;
	for(int _ = 0; _ < n; _++){
		int idx = -1;
		for(int i = 0; i < n; i++) if(!mk[i]) idx = i;
		if(idx == -1) continue;
		for(int i = 0; i < n; i++) if(!mk[i] && dis[i] < dis[idx]) idx = i;
		mk[idx] = 1;
		for(auto e : G[idx]){
			adj = A[e] ^ B[e] ^ idx;
			if(dis[idx] % S <= C[e] - L[e])
				w = dis[idx] + L[e];
			else 
				w = dis[idx] + (S - (dis[idx] % S)) + L[e];
			if(w < dis[adj])
				dis[adj] = w;
		}
	}
}

vl calculate_necessary_time(int _n, int _m, ll _S, int Q, vi _A, vi _B, vl _L, vl _C, vi _U, vi _V, vl _T) {
	n = _n; m = _m; S = _S;
	A = _A; B = _B; L = _L; C = _C;
	for(int i = 0; i < m; i++)
		G[A[i]].pb(i), G[B[i]].pb(i);

	vl ANS;
	for(int i = 0; i < Q; i++){
		Djik(_U[i], _T[i]);
		ANS.pb(dis[_V[i]] - _T[i]);
	}
	return ANS;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65080 KB Output is correct
2 Correct 41 ms 64928 KB Output is correct
3 Correct 50 ms 65060 KB Output is correct
4 Correct 33 ms 64964 KB Output is correct
5 Correct 42 ms 65048 KB Output is correct
6 Correct 38 ms 64944 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65080 KB Output is correct
2 Correct 41 ms 64928 KB Output is correct
3 Correct 50 ms 65060 KB Output is correct
4 Correct 33 ms 64964 KB Output is correct
5 Correct 42 ms 65048 KB Output is correct
6 Correct 38 ms 64944 KB Output is correct
7 Execution timed out 9071 ms 154960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65080 KB Output is correct
2 Correct 41 ms 64928 KB Output is correct
3 Correct 50 ms 65060 KB Output is correct
4 Correct 33 ms 64964 KB Output is correct
5 Correct 42 ms 65048 KB Output is correct
6 Correct 38 ms 64944 KB Output is correct
7 Execution timed out 9071 ms 154960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65080 KB Output is correct
2 Correct 41 ms 64928 KB Output is correct
3 Correct 50 ms 65060 KB Output is correct
4 Correct 33 ms 64964 KB Output is correct
5 Correct 42 ms 65048 KB Output is correct
6 Correct 38 ms 64944 KB Output is correct
7 Execution timed out 9071 ms 154960 KB Time limit exceeded
8 Halted 0 ms 0 KB -