oj.uz

Submission #422019

# Submission time Handle Problem Language Result Execution time Memory
422019 2021-06-09T14:54:30 Z oolimry Escape Route (JOI21_escape_route) C++17
0 / 100
 9000 ms 112004 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
 
lint byou;
vector<lint> dis0[95];
vector<lint> distest;
vector<pair<lint, vector<lint> > > changes[95];
bool done[95];
lint inf = (1LL << 59LL);
 
struct edge{
	lint to, L, C;
};
vector<edge> adj[95];
int n;
inline void relax(vector<lint> &dis, int a, int b, lint L, lint C){
	lint x = dis[a] % byou;
	if(x <= C-L) dis[b] = min(dis[b], dis[a] + L);
	else{
		lint t2 = ((dis[a]/byou) + 1) * byou + L;
		dis[b] = min(dis[b], t2);
	}
}

inline void dij(vector<lint> &dis, int st, lint T){
	fill(all(dis), inf);
	dis[st] = T;
	fill(done,done+n+1,0);
	for(int k = 0;k < n;k++){
		int mp = n;
		for(int i = 0;i < n;i++){
			if(not done[i] and dis[i] < dis[mp]) mp = i;
		}
		
		done[mp] = true;
		if(dis[mp] > byou) break;
		
		for(edge e : adj[mp]){
			if(not done[e.to]) relax(dis, mp, e.to, e.L, e.C);
		}
	}
}
 
vector<long long> calculate_necessary_time(int N, int m, long long SSS, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U,std::vector<int> V, std::vector<long long> T){
	byou = SSS;
	n = N;
	vector<lint> scam;
	for(int i = 0;i < Q;i++) scam.push_back(T[i]);
	sort(all(scam));
	
	for(int st = 0;st < n;st++){
		dis0[st].resize(n);
		fill(all(dis0[st]), inf);
		dis0[st][st] = 0;
		for(int k = 0;k < 2*n;k++){
			for(int i = 0;i < m;i++){
				relax(dis0[st], A[i], B[i], L[i], C[i]);
				relax(dis0[st], B[i], A[i], L[i], C[i]);
			}
		}
	}
	
	for(int i = 0;i < m;i++){
		adj[A[i]].push_back({B[i], L[i], C[i]});
		adj[B[i]].push_back({A[i], L[i], C[i]});
	}
	
	distest.resize(n+1);
	for(int a = 0;a < n;a++){
		for(int b = 0;b < n;b++){
			lint low = -1, high = byou+1;
			while(low != high-1){
				lint mid = (low+high)/2;
				
				fill(all(distest), inf);
				distest[a] = mid;
				fill(done,done+n+1,0);
				
				for(int k = 0;k < n;k++){
					int mp = n;
					for(int i = 0;i < n;i++){
						if(not done[i] and distest[i] < distest[mp]) mp = i;
					}
					
					done[mp] = true;
					if(mp == b) break;
					
					for(edge e : adj[mp]){
						if(not done[e.to]) relax(distest, mp, e.to, e.L, e.C);
					}
				}
				
				if(distest[b] < byou) low = mid;
				else high = mid;
			}
		}
	}
	
	for(int st = 0;st < n;st++){
		dij(distest, st, 0);
		
		lint curlow = 0;
		
		vector<lint> diffs(n);
		for(int i = 0;i < n;i++) diffs[i] = distest[i];
		for(int i = 0;i < n;i++) if(distest[i] >= byou) diffs[i] = inf;
		
		changes[st].push_back({0,diffs});
		
		while(curlow < byou){
			lint low = curlow, high = byou;
			while(low != high-1){
				lint mid = (low+high)/2;
				dij(distest, st, mid);
				
				for(int i = 0;i < n;i++) diffs[i] = distest[i] - mid;
				for(int i = 0;i < n;i++) if(distest[i] >= byou) diffs[i] = inf;		
				if(diffs != changes[st].back().second) high = mid;
				else low = mid;
			}
			
			curlow = high;
			dij(distest, st, curlow);
			for(int i = 0;i < n;i++) diffs[i] = distest[i] - curlow;
			for(int i = 0;i < n;i++) if(distest[i] >= byou) diffs[i] = inf;
			//for(int i = 0;i < n;i++) cerr << diffs[i] << " "; cerr << endl;
			changes[st].push_back({curlow,diffs});
			
			auto it = lower_bound(all(scam), curlow);
			if(it == scam.end()) break;
			else curlow = *it;
		}
	}
	
	vector<lint> ans(Q);
	
	for(int q = 0;q < Q;q++){
		
		pair<lint, vector<lint> > PP = {T[q], {inf+100}};
		auto it = upper_bound(all(changes[U[q]]), PP);
		it--;
		
		vector<lint> &v = it->second;
		//for(int x : v) cerr << x << " "; cerr << endl;
		
		lint res = v[V[q]];
		for(int u = 0;u < n;u++){
			if(v[u] < byou){
				res = min(res, byou + dis0[u][V[q]] - T[q]);
			}
		}
		
		ans[q] = res;
	}
	
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 64988 KB Output is correct
2 Correct 284 ms 65024 KB Output is correct
3 Incorrect 2492 ms 64944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 64988 KB Output is correct
2 Correct 284 ms 65024 KB Output is correct
3 Incorrect 2492 ms 64944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 64988 KB Output is correct
2 Correct 284 ms 65024 KB Output is correct
3 Incorrect 2492 ms 64944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 64988 KB Output is correct
2 Correct 284 ms 65024 KB Output is correct
3 Incorrect 2492 ms 64944 KB Output isn't correct
4 Halted 0 ms 0 KB -