oj.uz

Submission #422145

# Submission time Handle Problem Language Result Execution time Memory
422145 2021-06-09T18:52:19 Z errorgorn Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 228256 KB 
#include "escape_route.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll n,m,s,q;
 
struct edge{
	ll to;
	ll w;
	ll leave;
};
vector<edge> al[95];
 
 
ll w[95][4105][95]; //(u,time,v) go from u to v at t=time
vector<ll> t[95]; //the important times
 
 
ll w2[95][95]; //(u,time,v) if you start u at time 0
 
 
bool proc[95];
ll dw[95];
ii dw2[95];
 
std::vector<ll> calculate_necessary_time(
	int N, int M, ll S, int Q, std::vector<int> A, std::vector<int> B,
	std::vector<ll> L, std::vector<ll> C, std::vector<int> U,
	std::vector<int> V, std::vector<ll> T) {
		
	
	n=N,m=M,s=S,q=Q;
	rep(x,0,m){
		al[A[x]].pub(edge({B[x],L[x],C[x]-L[x]}));
		al[B[x]].pub(edge({A[x],L[x],C[x]-L[x]}));
	}
	
	rep(x,0,n){
		memset(dw2,63,sizeof(dw2));
		memset(proc,false,sizeof(proc));
		
		dw2[x]=ii(0,0);
		rep(y,0,n){
			ll curr=-1;
			rep(z,0,n) if (!proc[z] && (curr==-1 || dw2[z]<dw2[curr])) curr=z;
			proc[curr]=true;
			
			for (auto &it:al[curr]){
				ii temp=dw2[curr];
				if (temp.se<=it.leave) temp.se+=it.w;
				else temp=ii(temp.fi+1,it.w);
				
				dw2[it.to]=min(dw2[it.to],temp);
			}
		}
		
		rep(y,0,n) w2[x][y]=dw2[y].fi*s+dw2[y].se;
	}
	
	rep(x,0,n){
		ll ctime=0;
		int IDX=0;
		
		while (true){
			ll extra=1e18;
			
			memset(dw,63,sizeof(dw));
			memset(proc,false,sizeof(proc));
			
			dw[x]=ctime;
			rep(y,0,n){
				ll curr=-1;
				rep(z,0,n) if (!proc[z] && (curr==-1 || dw[z]<dw[curr])) curr=z;
				proc[curr]=true;
				
				for (auto &it:al[curr]){
					ll temp=dw[curr];
					if (temp<=it.leave){
						if (dw[it.to]>temp+it.w) extra=min(extra,it.leave-temp);
						temp+=it.w;
					}
					else temp=5e18;
					
					dw[it.to]=min(dw[it.to],temp);
				}
			}
			
			t[x].pub(ctime);
			rep(y,0,n) w[x][IDX][y]=dw[y];
			IDX++;
			
			if (extra==1e18) break;
			
			//cout<<ctime<<" "<<extra<<endl;
			
			ctime+=extra+1;
		}
	}
	
	/*
	rep(x,0,n){
		rep(y,0,n) cout<<w2[x][y]<<" "; cout<<endl;
	}
	//*/
	
	vector<ll> ans;
	
	rep(x,0,q){
		ll a=U[x],b=V[x],c=T[x];
		
		int iter=ub(all(t[a]),c)-t[a].begin()-1;
		
		ll res=w[a][iter][b]+(c-t[a][iter]);
		rep(y,0,n) if (w[a][iter][y]<1e18){
			res=min(res,w2[y][b]+s);
		}
		
		ans.pub(res-c);
	}
	
	//for (auto &it:ans) cout<<it<<" "; cout<<endl;
	
	return ans;
}

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:58:28: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   58 |   memset(dw2,63,sizeof(dw2));
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from escape_route.h:1,
                 from escape_route.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 38 ms 65040 KB Output is correct
3 Correct 135 ms 65012 KB Output is correct
4 Correct 28 ms 65064 KB Output is correct
5 Correct 29 ms 64972 KB Output is correct
6 Correct 29 ms 65068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1275 ms 127148 KB Output is correct
2 Correct 1194 ms 150492 KB Output is correct
3 Correct 921 ms 124560 KB Output is correct
4 Correct 1326 ms 153128 KB Output is correct
5 Correct 1339 ms 152992 KB Output is correct
6 Correct 28 ms 65024 KB Output is correct
7 Correct 948 ms 123512 KB Output is correct
8 Correct 664 ms 143460 KB Output is correct
9 Correct 1129 ms 121312 KB Output is correct
10 Correct 1366 ms 152380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 38 ms 65040 KB Output is correct
3 Correct 135 ms 65012 KB Output is correct
4 Correct 28 ms 65064 KB Output is correct
5 Correct 29 ms 64972 KB Output is correct
6 Correct 29 ms 65068 KB Output is correct
7 Correct 1275 ms 127148 KB Output is correct
8 Correct 1194 ms 150492 KB Output is correct
9 Correct 921 ms 124560 KB Output is correct
10 Correct 1326 ms 153128 KB Output is correct
11 Correct 1339 ms 152992 KB Output is correct
12 Correct 28 ms 65024 KB Output is correct
13 Correct 948 ms 123512 KB Output is correct
14 Correct 664 ms 143460 KB Output is correct
15 Correct 1129 ms 121312 KB Output is correct
16 Correct 1366 ms 152380 KB Output is correct
17 Correct 1552 ms 147800 KB Output is correct
18 Correct 1628 ms 149236 KB Output is correct
19 Correct 1350 ms 171904 KB Output is correct
20 Correct 1125 ms 140608 KB Output is correct
21 Correct 1684 ms 178704 KB Output is correct
22 Correct 1652 ms 178868 KB Output is correct
23 Correct 1107 ms 139812 KB Output is correct
24 Correct 794 ms 168844 KB Output is correct
25 Correct 1485 ms 137716 KB Output is correct
26 Correct 1771 ms 178864 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 38 ms 65040 KB Output is correct
3 Correct 135 ms 65012 KB Output is correct
4 Correct 28 ms 65064 KB Output is correct
5 Correct 29 ms 64972 KB Output is correct
6 Correct 29 ms 65068 KB Output is correct
7 Correct 1275 ms 127148 KB Output is correct
8 Correct 1194 ms 150492 KB Output is correct
9 Correct 921 ms 124560 KB Output is correct
10 Correct 1326 ms 153128 KB Output is correct
11 Correct 1339 ms 152992 KB Output is correct
12 Correct 28 ms 65024 KB Output is correct
13 Correct 948 ms 123512 KB Output is correct
14 Correct 664 ms 143460 KB Output is correct
15 Correct 1129 ms 121312 KB Output is correct
16 Correct 1366 ms 152380 KB Output is correct
17 Correct 1552 ms 147800 KB Output is correct
18 Correct 1628 ms 149236 KB Output is correct
19 Correct 1350 ms 171904 KB Output is correct
20 Correct 1125 ms 140608 KB Output is correct
21 Correct 1684 ms 178704 KB Output is correct
22 Correct 1652 ms 178868 KB Output is correct
23 Correct 1107 ms 139812 KB Output is correct
24 Correct 794 ms 168844 KB Output is correct
25 Correct 1485 ms 137716 KB Output is correct
26 Correct 1771 ms 178864 KB Output is correct
27 Correct 3991 ms 184500 KB Output is correct
28 Correct 4391 ms 193200 KB Output is correct
29 Correct 4176 ms 224080 KB Output is correct
30 Correct 2184 ms 147792 KB Output is correct
31 Correct 4845 ms 228256 KB Output is correct
32 Correct 4895 ms 225948 KB Output is correct
33 Correct 883 ms 159392 KB Output is correct
34 Correct 3689 ms 166012 KB Output is correct
35 Correct 4612 ms 215372 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 64972 KB Output is correct
2 Correct 38 ms 65040 KB Output is correct
3 Correct 135 ms 65012 KB Output is correct
4 Correct 28 ms 65064 KB Output is correct
5 Correct 29 ms 64972 KB Output is correct
6 Correct 29 ms 65068 KB Output is correct
7 Correct 1275 ms 127148 KB Output is correct
8 Correct 1194 ms 150492 KB Output is correct
9 Correct 921 ms 124560 KB Output is correct
10 Correct 1326 ms 153128 KB Output is correct
11 Correct 1339 ms 152992 KB Output is correct
12 Correct 28 ms 65024 KB Output is correct
13 Correct 948 ms 123512 KB Output is correct
14 Correct 664 ms 143460 KB Output is correct
15 Correct 1129 ms 121312 KB Output is correct
16 Correct 1366 ms 152380 KB Output is correct
17 Correct 1552 ms 147800 KB Output is correct
18 Correct 1628 ms 149236 KB Output is correct
19 Correct 1350 ms 171904 KB Output is correct
20 Correct 1125 ms 140608 KB Output is correct
21 Correct 1684 ms 178704 KB Output is correct
22 Correct 1652 ms 178868 KB Output is correct
23 Correct 1107 ms 139812 KB Output is correct
24 Correct 794 ms 168844 KB Output is correct
25 Correct 1485 ms 137716 KB Output is correct
26 Correct 1771 ms 178864 KB Output is correct
27 Correct 3991 ms 184500 KB Output is correct
28 Correct 4391 ms 193200 KB Output is correct
29 Correct 4176 ms 224080 KB Output is correct
30 Correct 2184 ms 147792 KB Output is correct
31 Correct 4845 ms 228256 KB Output is correct
32 Correct 4895 ms 225948 KB Output is correct
33 Correct 883 ms 159392 KB Output is correct
34 Correct 3689 ms 166012 KB Output is correct
35 Correct 4612 ms 215372 KB Output is correct
36 Execution timed out 9066 ms 167460 KB Time limit exceeded
37 Halted 0 ms 0 KB -