Submission #422153

#	Time	Username	Problem	Language	Result	Execution time	Memory
422153		errorgorn	Escape Route (JOI21_escape_route)	C++17	70 / 100	9029 ms	231012 KiB

escape_route

#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 (stderr)

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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30