Submission #422141

#	Time	Username	Problem	Language	Result	Execution time	Memory
422141		errorgorn	Escape Route (JOI21_escape_route)	C++17	70 / 100	9053 ms	329284 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){
    		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){
    						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 (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:58:32: 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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30