oj.uz

Submission #422134

# Submission time Handle Problem Language Result Execution time Memory
422134 2021-06-09T18:29:27 Z errorgorn Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 113224 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){
		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];
		
		memset(dw,63,sizeof(dw));
		memset(proc,false,sizeof(proc));
		
		dw[a]=c;
		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) temp+=it.w;
				else temp=5e18;
				
				dw[it.to]=min(dw[it.to],temp);
			}
		}
		
		ll res=dw[b];
		rep(y,0,n) if (dw[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 34 ms 64964 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 51 ms 65200 KB Output is correct
4 Correct 32 ms 65064 KB Output is correct
5 Correct 42 ms 64972 KB Output is correct
6 Correct 36 ms 65064 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9051 ms 113224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 64964 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 51 ms 65200 KB Output is correct
4 Correct 32 ms 65064 KB Output is correct
5 Correct 42 ms 64972 KB Output is correct
6 Correct 36 ms 65064 KB Output is correct
7 Execution timed out 9051 ms 113224 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 64964 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 51 ms 65200 KB Output is correct
4 Correct 32 ms 65064 KB Output is correct
5 Correct 42 ms 64972 KB Output is correct
6 Correct 36 ms 65064 KB Output is correct
7 Execution timed out 9051 ms 113224 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 64964 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 51 ms 65200 KB Output is correct
4 Correct 32 ms 65064 KB Output is correct
5 Correct 42 ms 64972 KB Output is correct
6 Correct 36 ms 65064 KB Output is correct
7 Execution timed out 9051 ms 113224 KB Time limit exceeded
8 Halted 0 ms 0 KB -