oj.uz

Submission #422152

# Submission time Handle Problem Language Result Execution time Memory
422152 2021-06-09T19:02:05 Z errorgorn Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 234488 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;
				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 32 ms 65148 KB Output is correct
2 Correct 39 ms 65084 KB Output is correct
3 Correct 97 ms 65104 KB Output is correct
4 Correct 30 ms 65036 KB Output is correct
5 Correct 30 ms 64972 KB Output is correct
6 Correct 30 ms 65056 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1101 ms 127428 KB Output is correct
2 Correct 1103 ms 150756 KB Output is correct
3 Correct 885 ms 124852 KB Output is correct
4 Correct 1229 ms 151968 KB Output is correct
5 Correct 1221 ms 151812 KB Output is correct
6 Correct 28 ms 64972 KB Output is correct
7 Correct 898 ms 123712 KB Output is correct
8 Correct 665 ms 142368 KB Output is correct
9 Correct 1030 ms 121712 KB Output is correct
10 Correct 1221 ms 151524 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65148 KB Output is correct
2 Correct 39 ms 65084 KB Output is correct
3 Correct 97 ms 65104 KB Output is correct
4 Correct 30 ms 65036 KB Output is correct
5 Correct 30 ms 64972 KB Output is correct
6 Correct 30 ms 65056 KB Output is correct
7 Correct 1101 ms 127428 KB Output is correct
8 Correct 1103 ms 150756 KB Output is correct
9 Correct 885 ms 124852 KB Output is correct
10 Correct 1229 ms 151968 KB Output is correct
11 Correct 1221 ms 151812 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 898 ms 123712 KB Output is correct
14 Correct 665 ms 142368 KB Output is correct
15 Correct 1030 ms 121712 KB Output is correct
16 Correct 1221 ms 151524 KB Output is correct
17 Correct 1506 ms 127964 KB Output is correct
18 Correct 1578 ms 129388 KB Output is correct
19 Correct 1248 ms 147064 KB Output is correct
20 Correct 1173 ms 120868 KB Output is correct
21 Correct 1650 ms 149044 KB Output is correct
22 Correct 1646 ms 148928 KB Output is correct
23 Correct 1065 ms 119788 KB Output is correct
24 Correct 755 ms 139104 KB Output is correct
25 Correct 1426 ms 117760 KB Output is correct
26 Correct 1633 ms 149080 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65148 KB Output is correct
2 Correct 39 ms 65084 KB Output is correct
3 Correct 97 ms 65104 KB Output is correct
4 Correct 30 ms 65036 KB Output is correct
5 Correct 30 ms 64972 KB Output is correct
6 Correct 30 ms 65056 KB Output is correct
7 Correct 1101 ms 127428 KB Output is correct
8 Correct 1103 ms 150756 KB Output is correct
9 Correct 885 ms 124852 KB Output is correct
10 Correct 1229 ms 151968 KB Output is correct
11 Correct 1221 ms 151812 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 898 ms 123712 KB Output is correct
14 Correct 665 ms 142368 KB Output is correct
15 Correct 1030 ms 121712 KB Output is correct
16 Correct 1221 ms 151524 KB Output is correct
17 Correct 1506 ms 127964 KB Output is correct
18 Correct 1578 ms 129388 KB Output is correct
19 Correct 1248 ms 147064 KB Output is correct
20 Correct 1173 ms 120868 KB Output is correct
21 Correct 1650 ms 149044 KB Output is correct
22 Correct 1646 ms 148928 KB Output is correct
23 Correct 1065 ms 119788 KB Output is correct
24 Correct 755 ms 139104 KB Output is correct
25 Correct 1426 ms 117760 KB Output is correct
26 Correct 1633 ms 149080 KB Output is correct
27 Correct 3189 ms 164232 KB Output is correct
28 Correct 3424 ms 173912 KB Output is correct
29 Correct 3233 ms 200292 KB Output is correct
30 Correct 1947 ms 130972 KB Output is correct
31 Correct 3763 ms 201896 KB Output is correct
32 Correct 3956 ms 202252 KB Output is correct
33 Correct 921 ms 140396 KB Output is correct
34 Correct 3027 ms 155372 KB Output is correct
35 Correct 3694 ms 200972 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65148 KB Output is correct
2 Correct 39 ms 65084 KB Output is correct
3 Correct 97 ms 65104 KB Output is correct
4 Correct 30 ms 65036 KB Output is correct
5 Correct 30 ms 64972 KB Output is correct
6 Correct 30 ms 65056 KB Output is correct
7 Correct 1101 ms 127428 KB Output is correct
8 Correct 1103 ms 150756 KB Output is correct
9 Correct 885 ms 124852 KB Output is correct
10 Correct 1229 ms 151968 KB Output is correct
11 Correct 1221 ms 151812 KB Output is correct
12 Correct 28 ms 64972 KB Output is correct
13 Correct 898 ms 123712 KB Output is correct
14 Correct 665 ms 142368 KB Output is correct
15 Correct 1030 ms 121712 KB Output is correct
16 Correct 1221 ms 151524 KB Output is correct
17 Correct 1506 ms 127964 KB Output is correct
18 Correct 1578 ms 129388 KB Output is correct
19 Correct 1248 ms 147064 KB Output is correct
20 Correct 1173 ms 120868 KB Output is correct
21 Correct 1650 ms 149044 KB Output is correct
22 Correct 1646 ms 148928 KB Output is correct
23 Correct 1065 ms 119788 KB Output is correct
24 Correct 755 ms 139104 KB Output is correct
25 Correct 1426 ms 117760 KB Output is correct
26 Correct 1633 ms 149080 KB Output is correct
27 Correct 3189 ms 164232 KB Output is correct
28 Correct 3424 ms 173912 KB Output is correct
29 Correct 3233 ms 200292 KB Output is correct
30 Correct 1947 ms 130972 KB Output is correct
31 Correct 3763 ms 201896 KB Output is correct
32 Correct 3956 ms 202252 KB Output is correct
33 Correct 921 ms 140396 KB Output is correct
34 Correct 3027 ms 155372 KB Output is correct
35 Correct 3694 ms 200972 KB Output is correct
36 Execution timed out 9114 ms 234488 KB Time limit exceeded
37 Halted 0 ms 0 KB -