oj.uz

Submission #519434

# Submission time Handle Problem Language Result Execution time Memory
519434 2022-01-26T10:56:10 Z fatemetmhr Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 219508 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){
	//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;
		}
		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);
    	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);
    	for(auto j : av[i]){
    		if(mn < t[j] - last){
    			last = t[j];
    			dij(i, last);
    			ans[j] = dis[v[j]];
    		}
    		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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 32 ms 64972 KB Output is correct
3 Correct 41 ms 65092 KB Output is correct
4 Correct 27 ms 65040 KB Output is correct
5 Correct 27 ms 64964 KB Output is correct
6 Correct 27 ms 64988 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2163 ms 193672 KB Output is correct
2 Correct 2113 ms 208056 KB Output is correct
3 Correct 2052 ms 199580 KB Output is correct
4 Correct 2160 ms 208524 KB Output is correct
5 Correct 2181 ms 207660 KB Output is correct
6 Correct 26 ms 64992 KB Output is correct
7 Correct 2070 ms 197212 KB Output is correct
8 Correct 1568 ms 219508 KB Output is correct
9 Correct 2036 ms 185000 KB Output is correct
10 Correct 2165 ms 206836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 32 ms 64972 KB Output is correct
3 Correct 41 ms 65092 KB Output is correct
4 Correct 27 ms 65040 KB Output is correct
5 Correct 27 ms 64964 KB Output is correct
6 Correct 27 ms 64988 KB Output is correct
7 Correct 2163 ms 193672 KB Output is correct
8 Correct 2113 ms 208056 KB Output is correct
9 Correct 2052 ms 199580 KB Output is correct
10 Correct 2160 ms 208524 KB Output is correct
11 Correct 2181 ms 207660 KB Output is correct
12 Correct 26 ms 64992 KB Output is correct
13 Correct 2070 ms 197212 KB Output is correct
14 Correct 1568 ms 219508 KB Output is correct
15 Correct 2036 ms 185000 KB Output is correct
16 Correct 2165 ms 206836 KB Output is correct
17 Correct 3794 ms 194324 KB Output is correct
18 Correct 3709 ms 193448 KB Output is correct
19 Correct 2642 ms 208264 KB Output is correct
20 Correct 3197 ms 198020 KB Output is correct
21 Correct 3583 ms 207612 KB Output is correct
22 Correct 3561 ms 207468 KB Output is correct
23 Correct 3320 ms 194000 KB Output is correct
24 Correct 1372 ms 217392 KB Output is correct
25 Correct 3542 ms 180872 KB Output is correct
26 Correct 3585 ms 204976 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 32 ms 64972 KB Output is correct
3 Correct 41 ms 65092 KB Output is correct
4 Correct 27 ms 65040 KB Output is correct
5 Correct 27 ms 64964 KB Output is correct
6 Correct 27 ms 64988 KB Output is correct
7 Correct 2163 ms 193672 KB Output is correct
8 Correct 2113 ms 208056 KB Output is correct
9 Correct 2052 ms 199580 KB Output is correct
10 Correct 2160 ms 208524 KB Output is correct
11 Correct 2181 ms 207660 KB Output is correct
12 Correct 26 ms 64992 KB Output is correct
13 Correct 2070 ms 197212 KB Output is correct
14 Correct 1568 ms 219508 KB Output is correct
15 Correct 2036 ms 185000 KB Output is correct
16 Correct 2165 ms 206836 KB Output is correct
17 Correct 3794 ms 194324 KB Output is correct
18 Correct 3709 ms 193448 KB Output is correct
19 Correct 2642 ms 208264 KB Output is correct
20 Correct 3197 ms 198020 KB Output is correct
21 Correct 3583 ms 207612 KB Output is correct
22 Correct 3561 ms 207468 KB Output is correct
23 Correct 3320 ms 194000 KB Output is correct
24 Correct 1372 ms 217392 KB Output is correct
25 Correct 3542 ms 180872 KB Output is correct
26 Correct 3585 ms 204976 KB Output is correct
27 Execution timed out 9038 ms 131104 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 32 ms 64972 KB Output is correct
3 Correct 41 ms 65092 KB Output is correct
4 Correct 27 ms 65040 KB Output is correct
5 Correct 27 ms 64964 KB Output is correct
6 Correct 27 ms 64988 KB Output is correct
7 Correct 2163 ms 193672 KB Output is correct
8 Correct 2113 ms 208056 KB Output is correct
9 Correct 2052 ms 199580 KB Output is correct
10 Correct 2160 ms 208524 KB Output is correct
11 Correct 2181 ms 207660 KB Output is correct
12 Correct 26 ms 64992 KB Output is correct
13 Correct 2070 ms 197212 KB Output is correct
14 Correct 1568 ms 219508 KB Output is correct
15 Correct 2036 ms 185000 KB Output is correct
16 Correct 2165 ms 206836 KB Output is correct
17 Correct 3794 ms 194324 KB Output is correct
18 Correct 3709 ms 193448 KB Output is correct
19 Correct 2642 ms 208264 KB Output is correct
20 Correct 3197 ms 198020 KB Output is correct
21 Correct 3583 ms 207612 KB Output is correct
22 Correct 3561 ms 207468 KB Output is correct
23 Correct 3320 ms 194000 KB Output is correct
24 Correct 1372 ms 217392 KB Output is correct
25 Correct 3542 ms 180872 KB Output is correct
26 Correct 3585 ms 204976 KB Output is correct
27 Execution timed out 9038 ms 131104 KB Time limit exceeded
28 Halted 0 ms 0 KB -