oj.uz

Submission #422153

# Submission time Handle Problem Language Result Execution time Memory
422153 2021-06-09T19:04:58 Z errorgorn Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 231012 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) sort(all(al[x]),[](edge &i,edge &j){
		return i.leave>j.leave;
	});
	
	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;
				if (dw[curr]>1e18) break;
				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 break;
					
					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:62: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]
   62 |   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 34 ms 65032 KB Output is correct
3 Correct 90 ms 65068 KB Output is correct
4 Correct 28 ms 65004 KB Output is correct
5 Correct 29 ms 65092 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1185 ms 127404 KB Output is correct
2 Correct 1059 ms 144192 KB Output is correct
3 Correct 870 ms 119832 KB Output is correct
4 Correct 1254 ms 147068 KB Output is correct
5 Correct 1209 ms 147048 KB Output is correct
6 Correct 28 ms 64968 KB Output is correct
7 Correct 874 ms 118848 KB Output is correct
8 Correct 646 ms 137464 KB Output is correct
9 Correct 1032 ms 116356 KB Output is correct
10 Correct 1208 ms 146092 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 34 ms 65032 KB Output is correct
3 Correct 90 ms 65068 KB Output is correct
4 Correct 28 ms 65004 KB Output is correct
5 Correct 29 ms 65092 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct
7 Correct 1185 ms 127404 KB Output is correct
8 Correct 1059 ms 144192 KB Output is correct
9 Correct 870 ms 119832 KB Output is correct
10 Correct 1254 ms 147068 KB Output is correct
11 Correct 1209 ms 147048 KB Output is correct
12 Correct 28 ms 64968 KB Output is correct
13 Correct 874 ms 118848 KB Output is correct
14 Correct 646 ms 137464 KB Output is correct
15 Correct 1032 ms 116356 KB Output is correct
16 Correct 1208 ms 146092 KB Output is correct
17 Correct 1438 ms 125840 KB Output is correct
18 Correct 1530 ms 127368 KB Output is correct
19 Correct 1201 ms 144544 KB Output is correct
20 Correct 1114 ms 118772 KB Output is correct
21 Correct 1559 ms 145600 KB Output is correct
22 Correct 1578 ms 145268 KB Output is correct
23 Correct 1057 ms 117456 KB Output is correct
24 Correct 791 ms 135544 KB Output is correct
25 Correct 1332 ms 115276 KB Output is correct
26 Correct 1565 ms 145392 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 34 ms 65032 KB Output is correct
3 Correct 90 ms 65068 KB Output is correct
4 Correct 28 ms 65004 KB Output is correct
5 Correct 29 ms 65092 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct
7 Correct 1185 ms 127404 KB Output is correct
8 Correct 1059 ms 144192 KB Output is correct
9 Correct 870 ms 119832 KB Output is correct
10 Correct 1254 ms 147068 KB Output is correct
11 Correct 1209 ms 147048 KB Output is correct
12 Correct 28 ms 64968 KB Output is correct
13 Correct 874 ms 118848 KB Output is correct
14 Correct 646 ms 137464 KB Output is correct
15 Correct 1032 ms 116356 KB Output is correct
16 Correct 1208 ms 146092 KB Output is correct
17 Correct 1438 ms 125840 KB Output is correct
18 Correct 1530 ms 127368 KB Output is correct
19 Correct 1201 ms 144544 KB Output is correct
20 Correct 1114 ms 118772 KB Output is correct
21 Correct 1559 ms 145600 KB Output is correct
22 Correct 1578 ms 145268 KB Output is correct
23 Correct 1057 ms 117456 KB Output is correct
24 Correct 791 ms 135544 KB Output is correct
25 Correct 1332 ms 115276 KB Output is correct
26 Correct 1565 ms 145392 KB Output is correct
27 Correct 2993 ms 161864 KB Output is correct
28 Correct 3218 ms 171264 KB Output is correct
29 Correct 2968 ms 197024 KB Output is correct
30 Correct 1719 ms 128076 KB Output is correct
31 Correct 3568 ms 197892 KB Output is correct
32 Correct 3580 ms 197816 KB Output is correct
33 Correct 856 ms 135032 KB Output is correct
34 Correct 2888 ms 150488 KB Output is correct
35 Correct 3491 ms 196064 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 34 ms 65032 KB Output is correct
3 Correct 90 ms 65068 KB Output is correct
4 Correct 28 ms 65004 KB Output is correct
5 Correct 29 ms 65092 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct
7 Correct 1185 ms 127404 KB Output is correct
8 Correct 1059 ms 144192 KB Output is correct
9 Correct 870 ms 119832 KB Output is correct
10 Correct 1254 ms 147068 KB Output is correct
11 Correct 1209 ms 147048 KB Output is correct
12 Correct 28 ms 64968 KB Output is correct
13 Correct 874 ms 118848 KB Output is correct
14 Correct 646 ms 137464 KB Output is correct
15 Correct 1032 ms 116356 KB Output is correct
16 Correct 1208 ms 146092 KB Output is correct
17 Correct 1438 ms 125840 KB Output is correct
18 Correct 1530 ms 127368 KB Output is correct
19 Correct 1201 ms 144544 KB Output is correct
20 Correct 1114 ms 118772 KB Output is correct
21 Correct 1559 ms 145600 KB Output is correct
22 Correct 1578 ms 145268 KB Output is correct
23 Correct 1057 ms 117456 KB Output is correct
24 Correct 791 ms 135544 KB Output is correct
25 Correct 1332 ms 115276 KB Output is correct
26 Correct 1565 ms 145392 KB Output is correct
27 Correct 2993 ms 161864 KB Output is correct
28 Correct 3218 ms 171264 KB Output is correct
29 Correct 2968 ms 197024 KB Output is correct
30 Correct 1719 ms 128076 KB Output is correct
31 Correct 3568 ms 197892 KB Output is correct
32 Correct 3580 ms 197816 KB Output is correct
33 Correct 856 ms 135032 KB Output is correct
34 Correct 2888 ms 150488 KB Output is correct
35 Correct 3491 ms 196064 KB Output is correct
36 Execution timed out 9029 ms 231012 KB Time limit exceeded
37 Halted 0 ms 0 KB -