Submission #211591

#	Time	Username	Problem	Language	Result	Execution time	Memory
211591		NachoLibre	Commuter Pass (JOI18_commuter_pass)	C++14	55 / 100	1667 ms	25660 KiB

commuter_pass

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

const int N = 100005, M = 200005;
const long long inf = 1e18;
int n, m, s, t, u, v, x, y, z, mv[N][2];
vector<int> e[N][2];
vector<long long> o[302];
long long fp = inf;

int rnd() {
	int dr = (int)rand() % 100000 * 10000 + (int)rand() % 100000;
	return (dr % n == 0 ? n : dr % n);
}

vector<long long> D(int rt) {
	vector<long long> dr;
	dr.resize(n + 1, inf);
	dr[rt] = 0;
	mv[rt][0] = mv[rt][1] = 0;
	set<pair<long long, int> > s;
	s.insert({0, rt});
	while(s.size()) {
		int dg = (*s.begin()).second;
		long long mn = (*s.begin()).first;
		s.erase(s.begin());
		for(int i = 0; i < e[dg][0].size(); ++i) {
			if(mn + e[dg][1][i] < dr[e[dg][0][i]]) {
				if(dr[e[dg][0][i]] ^ inf) s.erase(s.find({dr[e[dg][0][i]], e[dg][0][i]}));
				mv[e[dg][0][i]][0] = dg;
				mv[e[dg][0][i]][1] = i;
				dr[e[dg][0][i]] = mn + e[dg][1][i];
				s.insert({dr[e[dg][0][i]], e[dg][0][i]});
			}
		}
	}
	return dr;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	srand(time(NULL));
	cin >> n >> m >> s >> t >> u >> v;
	for(int i = 1; i <= m; ++i) {
		cin >> x >> y >> z;
		e[x][0].push_back(y);
		e[x][1].push_back(z);
		e[y][0].push_back(x);
		e[y][1].push_back(z);
	}
	o[0] = D(s);
	o[1] = D(t);
	o[2] = D(u);
	o[3] = D(v);
	for(int tr = 1; tr <= 5; ++tr) {
		int rw = rnd();
		o[4] = D(rw);
		for(int i = 1; i <= n; ++i) {
			if(o[0][rw] + o[4][i] + o[1][i] == o[0][t]) {
				fp = min(fp, min(o[2][rw] + o[3][i], o[2][i] + o[3][rw]));
			}
		}
	}
	if(n <= 300) {
		for(int i = 1; i <= n; ++i) {
			o[i] = D(i);
		}
		fp = min(fp, o[u][v]);
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= n; ++j) {
				if(o[s][t] == o[s][i] + o[i][j] + o[j][t]) {
					fp = min(fp, min(o[u][i] + o[j][v], o[u][j] + o[i][v]));
				}
			}
		}
	} else if(s == u) {
		o[0] = D(s);
		o[1] = D(t);
		o[2] = D(u);
		o[3] = D(v);
		fp = min(fp, o[0][v]);
		for(int i = 1; i <= n; ++i) {
			if(o[0][i] + o[1][i] == o[0][t]) {
				fp = min(fp, o[3][i]);
			}
		}
	} else {
		D(s);
		int dg = t;
		while(dg ^ s) {
			e[mv[dg][0]][1][mv[dg][1]] = 0;
			for(int i = 0; i < e[dg][0].size(); ++i) {
				if(e[dg][0][i] == mv[dg][0]) {
					e[dg][1][i] = 0;
					break;
				}
			}
			dg = mv[dg][0];
		}
		fp = min(fp, D(u)[v]);
	}
	cout << fp << endl;
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> D(int)':
commuter_pass.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < e[dg][0].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:93:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < e[dg][0].size(); ++i) {
                   ~~^~~~~~~~~~~~~~~~~

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