Submission #1269126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269126		_rain_	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	263 ms	14972 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1)<<(x))
#define sz(x) (int)(x).size()
#define Time_used cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 1e5;
const int M = (int) 2e5;
const LL inf = (LL)1e18;
	int x[M + 2] , y[M + 2] , c[M + 2];
	int n , m;
	int source , sink , n_source , n_sink;
	
namespace subtask1{
	bool check(){
		return n <= 300;
	}
	
	const int maxn = 300;
		LL f[maxn + 2][maxn + 2];
	
	void main_code(){
		memset(f,0x3f,sizeof f);
		for(int i = 1; i <= n; ++i) f[i][i] = 0;
		for(int i = 1; i <= m; ++i){
			minimize(f[x[i]][y[i]] , c[i]);
			minimize(f[y[i]][x[i]] , c[i]);
		}
		for(int k = 1; k <= n; ++k){
			for(int i = 1; i <= n; ++i) {
				for(int j = 1; j <= n; ++j) {
					minimize(f[i][j] , f[i][k] + f[k][j]);
				}
			}
		}
		
		LL min_dist = f[source][sink];
		LL ans = f[n_source][n_sink];
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= n; ++j){
				if (f[source][i] + f[i][j] + f[j][sink] == min_dist){
					minimize(ans , f[n_source][i] + f[j][n_sink]);
					minimize(ans , f[n_sink][i] + f[j][n_source]);
				}
			}
		}
		cout << ans << '\n';
		return;
	}
}

namespace subtask2{
	bool check(){
		return true;
	}
	
	vector<int> ke[N + 2];	
		void add_canh(int u , int v , int id){
			ke[u].push_back(id) , ke[v].push_back(id);
			return;
		}
	
		void build_djisktra(int source , LL d[]){
			for(int i = 1; i <= n; ++i) d[i] = inf;
			priority_queue<pair<LL,int> , vector<pair<LL,int>> , greater<pair<LL,int>>> pq;
			d[source] = 0;
			pq.push({d[source] , source});
			while (pq.size()){
				int u = pq.top().second;
				LL cost = pq.top().first;
				pq.pop();
				if (cost != d[u]) continue;
				for(int id : ke[u]){
					int v = x[id] ^ y[id] ^ u;
					if (minimize(d[v] , cost + c[id])){
						pq.push({d[v] , v});
					}
				}
			}
			return;
		}
	
	LL tmp[N + 2] = {} , d[N + 2] = {} , rev_dist[N + 2] = {};
	
		LL process(int source , int sink){
				build_djisktra(source , d);
				build_djisktra(sink , rev_dist);
			LL min_dist = d[sink];
			for(int i = 1; i <= n; ++i) tmp[i] = inf;
			priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>>pq;
			tmp[n_source] = 0;
			pq.push({tmp[n_source] , n_source});
			while (sz(pq)){
				int u = pq.top().second;
				LL cost = pq.top().first;
				pq.pop();
				if (cost != tmp[u]) continue;
				for(int id : ke[u]){
					int v = u ^ x[id] ^ y[id];
					LL cost_change = (d[u] + rev_dist[v] + c[id] == min_dist ? 0 : c[id]);
					if (minimize(tmp[v] , cost + cost_change)) pq.push({tmp[v] , v});
				}
			}
			return tmp[n_sink];
		}
	
	void main_code(){
		for(int i = 1; i <= m; ++i) add_canh(x[i] , y[i] , i);
		cout << min(process(source , sink) , process(sink , source));
		return ;
	}
}

int main(){
	ios :: sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> m;
		cin >> source >> sink;
		cin >> n_source >> n_sink;
		
		for(int i = 1; i <= m; ++i) cin >> x[i] >> y[i] >> c[i];
		if (subtask1::check()) return subtask1::main_code() , 0;
		if (subtask2::check()) return subtask2::main_code() , 0;
		
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:141:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:142:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45