Submission #396418

#	Time	Username	Problem	Language	Result	Execution time	Memory
396418		ChrisT	Escape Route (JOI21_escape_route)	C++17	35 / 100	9026 ms	150160 KiB

escape_route

#include <bits/stdc++.h>
using namespace std;
const int MN = 60 + 1;
long long pre[MN][MN*MN][MN], stop[MN][MN];
vector<long long> times[MN];
long long adj[MN][MN], bad[MN][MN];
bool vis[MN];
vector<long long> calculate_necessary_time (int n, int m, long long s, int q, vector<int> a, vector<int> b, vector<long long> l, vector<long long> c, vector<int> u, vector<int> v, vector<long long> T) {
	memset(adj,0x3f,sizeof adj);
	for (int i = 0; i < m; i++) {
		adj[++a[i]][++b[i]] = l[i];
		adj[b[i]][a[i]] = l[i];
		bad[a[i]][b[i]] = bad[b[i]][a[i]] = c[i];
	}
	for (int st = 1; st <= n; st++) {
		memset(stop[st],0x3f,sizeof stop[st]); memset(vis,0,sizeof vis);
		stop[st][st] = 0;
		for (int iter = 0; iter < n; iter++) {
			int mn = -1;
			for (int i = 1; i <= n; i++) if (!vis[i] && (mn == -1 || stop[st][i] < stop[st][mn])) mn = i;
			if (mn == -1 || stop[st][mn] > 1e18) break;
			vis[mn] = true;
			for (int i = 1; i <= n; i++) if (adj[mn][i] < 1e18) {
				long long att = stop[st][mn];
				if (att%s <= bad[mn][i] - adj[mn][i]) att += adj[mn][i];
				else att += (s - att%s) + adj[mn][i];
				stop[st][i] = min(stop[st][i],att);
			}
		}
	}
	for (int st = 1; st <= n; st++) { //no stop all go
		times[st].push_back(0);
		for (int id = 0; id < (int)times[st].size(); id++) {
			long long t = times[st][id];
			memset(pre[st][id],0x3f,sizeof pre[st][id]);
			memset(vis,0,sizeof vis);
			pre[st][id][st] = t;
			for (int iter = 0; iter < n; iter++) {
				int mn = -1;
				for (int i = 1; i <= n; i++) if (!vis[i] && (mn == -1 || pre[st][id][i] < pre[st][id][mn])) mn = i;
				if (mn == -1 || pre[st][id][mn] > 1e18) break;
				vis[mn] = true;
				for (int i = 1; i <= n; i++) if (adj[mn][i] < 1e18) {
					long long att = pre[st][id][mn];
					if (att%s <= bad[mn][i] - adj[mn][i]) att += adj[mn][i];
					else continue; //no stop
					pre[st][id][i] = min(pre[st][id][i],att);
				}
			}
			long long nextTime = 1e18 + 5;
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) if (adj[i][j] < 1e18 && pre[st][id][i] < 1e18 && pre[st][id][j] < 1e18) {
					long long md = pre[st][id][i]%s;
					if (md <= bad[i][j] - adj[i][j]) nextTime = min(nextTime,bad[i][j] - adj[i][j] + 1 - md + t);
				}
			}
			if (nextTime < s) times[st].push_back(nextTime);
		}
	}
	vector<long long> ret(q);
	for (int i = 0; i < q; i++) {
		++u[i]; ++v[i];
		int id = upper_bound(times[u[i]].begin(),times[u[i]].end(),T[i]) - times[u[i]].begin() - 1;
		long long t = times[u[i]][id];
		ret[i] = pre[u[i]][id][v[i]] - t;
		for (int ed = 1; ed <= n; ed++) {
			long long att = pre[u[i]][id][ed] + T[i] - t;
			att = (att + s - 1) / s * s;
			ret[i] = min(ret[i],att+stop[ed][v[i]]-T[i]);
		}
	}
	return ret;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30