oj.uz

Submission #520659

# Submission time Handle Problem Language Result Execution time Memory
520659 2022-01-30T16:26:48 Z fatemetmhr Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 243828 KB 
//  ~Be name khoda~  //
 
#include "escape_route.h"
#include<bits/stdc++.h>
 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'
 
const int maxn  =  1e6   + 10;
const int maxn5 =  91;
const int maxq  =  3e6   + 5;
const int maxe  =  4e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;
 
ll t[maxq], c[maxe], l[maxe];
int u[maxq], v[maxq];
int a[maxe], b[maxe];
int n, m, q;
ll s, ans[maxq], mn, tim[maxn5];
bool ok[maxn5], done[maxn5];
ll dis[maxn5], with0[maxn5][maxn5];
int adj[maxn5][maxn5];
vector <int> av[maxn5];

 
inline bool cmp(int i, int j){return t[i] < t[j];}
 
inline void fix(ll &a){
	if(a >= s)
		a -= s;
}
 
inline void dij(int v, ll ti, bool con){
	//cout << "hola " << v << ' ' << ti << endl;
	memset(dis, -1, sizeof dis);
	memset(done, false, sizeof done);
	memset(ok, false, sizeof ok);
	dis[v] = 0;
	tim[v] = ti;
	ok[v] = true;
	
	mn = inf;
	for(int i = 0; i < n; i++){
		int v = -1;
		for(int j = 0; j < n; j++) if(!done[j] && dis[j] > -1 && (v == -1 || dis[j] < dis[v])){
			v = j;
		}
		if(!ok[v] && !con)
			break;
		done[v] = true;
		//cout << "ok " << v << ' ' << dis[v] << ' ' << tim[v] << endl;
		for(int j = 0; j < n; j++) if(adj[v][j] != -1 && !done[j]){
			ll len;
			if(tim[v] <= c[adj[v][j]] - l[adj[v][j]]){
				if(ok[v]){
					ok[j] = true;
					mn = min(mn, c[adj[v][j]] - l[adj[v][j]] - tim[v]);
				}
				len = l[adj[v][j]];
			}
			else{
				len = s - tim[v] + l[adj[v][j]];
			}
			//cout << v << ' ' << j << ' ' << len << ' ' << adj[v][j] << ' ' << l[adj[v][j]] << endl;
			if(dis[j] == -1 || dis[j] > dis[v] + len){
				dis[j] = dis[v] + len;
				tim[j] = tim[v] + len;
				fix(tim[j]);
			}
		}
	}
	return;
}
 
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) {
    
    n = N;
    m = M;
    s = S;
    q = Q;
    memset(adj, -1, sizeof adj);
    for(int i = 0; i < m; i++){
    	a[i] = A[i];
    	b[i] = B[i];
    	l[i] = L[i];
    	c[i] = C[i];
    	adj[a[i]][b[i]] = adj[b[i]][a[i]] = i;
    }
    for(int i = 0; i < q; i++){
    	u[i] = U[i];
    	v[i] = V[i];
    	t[i] = T[i];
    	av[u[i]].pb(i);
    }
    //*
    for(int i = 0; i < n; i++){
    	dij(i, 0, true);
    	for(int j = 0; j < n; j++)
    		with0[i][j] = dis[j];
    }
    //*/
    
    for(int i = 0; i < n; i++){
    	sort(all(av[i]), cmp);
    	ll last = 0;
    	dij(i, 0, true);
    	for(auto j : av[i]){
    		if(mn < t[j] - last){
    			last = t[j];
    			dij(i, last, false);
    		}
    		else
    			mn -= (t[j] - last);
			ans[j] = inf;
			for(int z = 0; z < n; z++) if(ok[z]){
				if(z == v[j])
					ans[j] = min(ans[j], dis[z]);
				ans[j] = min(ans[j], dis[z] + s - (tim[z] + (t[j] - last)) + with0[z][v[j]]);
			}
    	}
    }
    
    vector <long long> ret;
    for(int i = 0; i < q; i++)
    	ret.pb(ans[i]);
    
    return ret;
}

Compilation message

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:128:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  128 |       else
      |       ^~~~
escape_route.cpp:130:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  130 |    ans[j] = inf;
      |    ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64972 KB Output is correct
2 Correct 29 ms 64992 KB Output is correct
3 Correct 38 ms 65072 KB Output is correct
4 Correct 26 ms 65028 KB Output is correct
5 Correct 27 ms 65032 KB Output is correct
6 Correct 26 ms 65016 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2126 ms 188360 KB Output is correct
2 Correct 2029 ms 202560 KB Output is correct
3 Correct 2045 ms 194152 KB Output is correct
4 Correct 2195 ms 203568 KB Output is correct
5 Correct 2111 ms 203612 KB Output is correct
6 Correct 24 ms 64972 KB Output is correct
7 Correct 2099 ms 211264 KB Output is correct
8 Correct 1752 ms 243828 KB Output is correct
9 Correct 2217 ms 199268 KB Output is correct
10 Correct 2454 ms 230956 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64972 KB Output is correct
2 Correct 29 ms 64992 KB Output is correct
3 Correct 38 ms 65072 KB Output is correct
4 Correct 26 ms 65028 KB Output is correct
5 Correct 27 ms 65032 KB Output is correct
6 Correct 26 ms 65016 KB Output is correct
7 Correct 2126 ms 188360 KB Output is correct
8 Correct 2029 ms 202560 KB Output is correct
9 Correct 2045 ms 194152 KB Output is correct
10 Correct 2195 ms 203568 KB Output is correct
11 Correct 2111 ms 203612 KB Output is correct
12 Correct 24 ms 64972 KB Output is correct
13 Correct 2099 ms 211264 KB Output is correct
14 Correct 1752 ms 243828 KB Output is correct
15 Correct 2217 ms 199268 KB Output is correct
16 Correct 2454 ms 230956 KB Output is correct
17 Correct 4162 ms 209896 KB Output is correct
18 Correct 3793 ms 208888 KB Output is correct
19 Correct 2685 ms 228436 KB Output is correct
20 Correct 3147 ms 213072 KB Output is correct
21 Correct 3584 ms 230840 KB Output is correct
22 Correct 3567 ms 230184 KB Output is correct
23 Correct 3222 ms 208828 KB Output is correct
24 Correct 1323 ms 239844 KB Output is correct
25 Correct 3525 ms 196232 KB Output is correct
26 Correct 3522 ms 225192 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64972 KB Output is correct
2 Correct 29 ms 64992 KB Output is correct
3 Correct 38 ms 65072 KB Output is correct
4 Correct 26 ms 65028 KB Output is correct
5 Correct 27 ms 65032 KB Output is correct
6 Correct 26 ms 65016 KB Output is correct
7 Correct 2126 ms 188360 KB Output is correct
8 Correct 2029 ms 202560 KB Output is correct
9 Correct 2045 ms 194152 KB Output is correct
10 Correct 2195 ms 203568 KB Output is correct
11 Correct 2111 ms 203612 KB Output is correct
12 Correct 24 ms 64972 KB Output is correct
13 Correct 2099 ms 211264 KB Output is correct
14 Correct 1752 ms 243828 KB Output is correct
15 Correct 2217 ms 199268 KB Output is correct
16 Correct 2454 ms 230956 KB Output is correct
17 Correct 4162 ms 209896 KB Output is correct
18 Correct 3793 ms 208888 KB Output is correct
19 Correct 2685 ms 228436 KB Output is correct
20 Correct 3147 ms 213072 KB Output is correct
21 Correct 3584 ms 230840 KB Output is correct
22 Correct 3567 ms 230184 KB Output is correct
23 Correct 3222 ms 208828 KB Output is correct
24 Correct 1323 ms 239844 KB Output is correct
25 Correct 3525 ms 196232 KB Output is correct
26 Correct 3522 ms 225192 KB Output is correct
27 Execution timed out 9026 ms 145472 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64972 KB Output is correct
2 Correct 29 ms 64992 KB Output is correct
3 Correct 38 ms 65072 KB Output is correct
4 Correct 26 ms 65028 KB Output is correct
5 Correct 27 ms 65032 KB Output is correct
6 Correct 26 ms 65016 KB Output is correct
7 Correct 2126 ms 188360 KB Output is correct
8 Correct 2029 ms 202560 KB Output is correct
9 Correct 2045 ms 194152 KB Output is correct
10 Correct 2195 ms 203568 KB Output is correct
11 Correct 2111 ms 203612 KB Output is correct
12 Correct 24 ms 64972 KB Output is correct
13 Correct 2099 ms 211264 KB Output is correct
14 Correct 1752 ms 243828 KB Output is correct
15 Correct 2217 ms 199268 KB Output is correct
16 Correct 2454 ms 230956 KB Output is correct
17 Correct 4162 ms 209896 KB Output is correct
18 Correct 3793 ms 208888 KB Output is correct
19 Correct 2685 ms 228436 KB Output is correct
20 Correct 3147 ms 213072 KB Output is correct
21 Correct 3584 ms 230840 KB Output is correct
22 Correct 3567 ms 230184 KB Output is correct
23 Correct 3222 ms 208828 KB Output is correct
24 Correct 1323 ms 239844 KB Output is correct
25 Correct 3525 ms 196232 KB Output is correct
26 Correct 3522 ms 225192 KB Output is correct
27 Execution timed out 9026 ms 145472 KB Time limit exceeded
28 Halted 0 ms 0 KB -